LeetCode 1014 Best Sightseeing Pair (Enumerate Right Maintain Left)

Original Problem#

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

Idea#

Double loop enumeration

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;
    }
};

But it cannot pass all test cases. The time complexity is too high $O(n^2)$ .

Solution#

Idea: Reduce complexity. Find a way to achieve a complexity of $O(n)$ .

Rearranging the objective function gives (value[i] + i) + (value[j] - j), then treat value[i] + i as a whole and value[j] - j as another whole. This transforms it into finding the maximum of two numbers.

Consider iterating over j while maintaining the maximum value of value[i] + i, so the code can be changed to

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;
    }
};

Enumerate Right to Maintain Left#

For problems similar to the double variable problem shown in leetcode 1014, you can choose to enumerate the right index $j$ to transform it into a single variable problem for solving.

For similar problems, refer to https://leetcode.cn/circle/discuss/mOr1u6/