[LeetCode] 1014. Best Sightseeing Pair explained

Problem

1014. Best Sightseeing Pair

Approach

Note that the score value consists of two parts.
We are going to find the index of best left pair as we iterate through the values, and cache them in maxLeftScore.

• i: index of left pair candidate.
• j: index of right pair candidate.

At each time we move j,

1. Can index j-1 can be the new i? Then update maxLeftScore.
2. Update maxScore value with max(maxScore, score(i,j)).

Code

typedef vector<int> vi;

class Solution {
public:
    static inline int maxScoreSightseeingPair(vi &values) {
        int n= values.size(), maxLeftScore= 0, maxScore= 0;
        for (int j=1; j < n; ++j) {
            maxLeftScore= max(maxLeftScore, values[j-1]+j-1);
            maxScore= max(maxScore, values[j]-j+maxLeftScore);
        }
        return maxScore;
    }
};

Complexity

• Time: \(O(N)\)
• Space: \(O(1)\)