## 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