O(1) Space | O(N) Time | Single Pass | Beats 100%
IntuitionNote: In these type of problems, it is always likely to convert the given array(nums) into nums[i] (+/-) i.
i.e. update nums[i] to nums[i] + i, and the
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
**Note**: In these type of problems, it is always likely to convert the given array(nums) into nums[i] (+/-) i. 
i.e. update nums[i] to nums[i] + i, and then appraoch problem. 
- We have to maximize the value of values[i] + values[j] + (i - j). We can rewrite this as **(values[i] + i) + (values[j] - j)**. 
- Now we can calculate both values for each index i.e (values[i] + i) and (values[i] - i). 
- Note for any index i, we will find best j as **max(values[j] - j) for j > i**. 
- Here we can notice that for every i, we need the maximum value from the **suffix**. 

---


# Approach
<!-- Describe your approach to solving the problem. -->
- Start iterating from the back, keep track of the maximum value of (values[i] - i). Call it **suffixMax**. 
- For each index, calculate **values[i] + i + suffixMax**, and update the answer if this value is greater than answer. 


---



# Complexity
- $$ Time Complexity: O(N) $$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- $$ Space Complexity: O(1) $$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:

    const int INF = 1e9; 

    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size(), ans = -INF; 
        int suffixMax = values[n - 1] - n + 1; 
        for (int i = n - 2; i >= 0; i--) {
            ans = max(ans, values[i] + i + suffixMax); 
            suffixMax = max(suffixMax, values[i] - i); 
        }
        return ans; 
    }
};
```
['Array', 'Dynamic Programming', 'C++']