leetcode 1014 最佳观光组合（枚举右维护左）

原题#

https://leetcode.cn/problems/best-sightseeing-pair/description/

思路#

双循环枚举

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int max = 0;
        int length = values.size();
        for(int i = 0; i < length; ++i)
            for(int j = i + 1; j < length; ++j)
                if(values[i] + values[j] + i - j > max)
                    max = values[i] + values[j] + i - j;
        return max;
    }
};

但不能通过全部测试点。时间复杂度过高 $O(n^2)$

题解#

思路：降低复杂度。想办法弄成 $O(n)$ 的复杂度就好了。

目标函数移项得到 (value[i] + i) + (value[j] - j) ，然后将 value[i] + i 当做整体，将 value[j] - j 当做整体。就转化为了两数的最大值。

考虑遍历 j 然后维护 value[i] + i 的最大值，所以代码可以变为

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0;
        int mx = 0;
        for(int j = 0; j < values.size(); ++j){
            ans = max(ans, mx + values[j] - j); 
            mx = max(mx, values[j] + j);
        }
        return ans;
    }
};

枚举右维护左#

对于类似 leetcode 1014 所示的双变量问题，可以选择枚举右下标 $j$ ，来转化为单变量问题求解。

类似题目参看 https://leetcode.cn/circle/discuss/mOr1u6/