1014. Best Sightseeing Pair

You are given an integer array values where values[i] represents the value of the $i^{th}$ sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.
 

Example 1:

Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2:

Input: values = [1,2]
Output: 2

Constraints:

• $2<=values.length<=5\ast 10^4$
• 1 <= values[i] <= 1000

From: LeetCode
Link: 1014. Best Sightseeing Pair

Solution:

Ideas:

We rewrite the formula:

$$values[i]+values[j]+i-j=(values[i]+i)+(values[j]-j)$$

So while scanning j from left to right:

• keep the best previous value of values[i] + i

• compute current score with best + values[j] - j

• update the answer

• then update best

Code:

int maxScoreSightseeingPair(int* values, int valuesSize) {
    int best = values[0] + 0;   // best value of values[i] + i so far
    int ans = 0;

    for (int j = 1; j < valuesSize; j++) {
        int score = best + values[j] - j;   // (values[i] + i) + (values[j] - j)
        if (score > ans) {
            ans = score;
        }

        int candidate = values[j] + j;
        if (candidate > best) {
            best = candidate;
        }
    }

    return ans;
}