Best Sightseeing Pair
Problem
For indices i < j, the sightseeing pair score is values[i] + values[j] + i − j. Return the maximum score.
values = [8,1,5,2,6]11def maxScoreSightseeingPair(values):
best = 0
ans = 0
for j, v in enumerate(values):
ans = max(ans, best + v - j)
best = max(best, v + j)
return ansfunction maxScoreSightseeingPair(values) {
let best = 0, ans = 0;
for (let j = 0; j < values.length; j++) {
ans = Math.max(ans, best + values[j] - j);
best = Math.max(best, values[j] + j);
}
return ans;
}class Solution {
public int maxScoreSightseeingPair(int[] values) {
int best = 0, ans = 0;
for (int j = 0; j < values.length; j++) {
ans = Math.max(ans, best + values[j] - j);
best = Math.max(best, values[j] + j);
}
return ans;
}
}int maxScoreSightseeingPair(vector<int>& values) {
int best = 0, ans = 0;
for (int j = 0; j < (int)values.size(); j++) {
ans = max(ans, best + values[j] - j);
best = max(best, values[j] + j);
}
return ans;
}Explanation
The pair score is values[i] + values[j] + i - j for i < j. The clever move is to split it into a part that only depends on the left spot and a part that only depends on the right spot: (values[i] + i) and (values[j] - j).
Now for any right index j, the best possible score is just (best left value so far) + (values[j] - j). So we never need to compare all pairs — we only need the best left value seen before j.
We scan left to right keeping best = max(values[i] + i) over all earlier i. At each j we update the answer with best + values[j] - j, then fold j itself into best so it can serve as a left spot for future indices.
Because each step is a couple of max updates, the whole thing is a single linear pass.
Example: values = [8,1,5,2,6]. The left part v+i peaks at index 0 (8+0=8); pairing it with j = 4 gives 8 + 6 - 4 = 10, and the running best ends at 11.