## Original Problem#

https://leetcode.cn/problems/best-sightseeing-pair/description/

## Idea#

Double loop enumeration

```
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int max = 0;
int length = values.size();
for(int i = 0; i < length; ++i)
for(int j = i + 1; j < length; ++j)
if(values[i] + values[j] + i - j > max)
max = values[i] + values[j] + i - j;
return max;
}
};
```

But it cannot pass all test cases. The time complexity is too high $O(n^2)$.

## Solution#

Idea: Reduce complexity. Find a way to achieve a complexity of $O(n)$.

Rearranging the objective function gives `(value[i] + i) + (value[j] - j)`

, then treat `value[i] + i`

as a whole and `value[j] - j`

as another whole. This transforms it into finding the maximum of two numbers.

Consider iterating over `j`

while maintaining the maximum value of `value[i] + i`

, so the code can be changed to

```
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int ans = 0;
int mx = 0;
for(int j = 0; j < values.size(); ++j){
ans = max(ans, mx + values[j] - j);
mx = max(mx, values[j] + j);
}
return ans;
}
};
```

## Enumerate Right to Maintain Left#

For problems similar to the double variable problem shown in leetcode 1014, you can choose to enumerate the right index $j$ to transform it into a single variable problem for solving.

For similar problems, refer to https://leetcode.cn/circle/discuss/mOr1u6/