Problem
Key Idea
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))
.
- Time: \(O(N)\)
- Space: \(O(1)\)
Implementation
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;
}
};
Leave a comment