Easy | Simple Greedy | C++ | O(n) | 100% Beat
IntuitionBy the problem statement we know that for maximize final answer we have to maximize the difference between values and minimize the position difference.
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
By the problem statement we know that for maximize final answer we have to maximize the difference between values and minimize the position difference.
So, After some analysis i get to know that for any index `i` we require maximum value of `X=arr[j]-j` where `j>i`. so final answer will be max of `arr[i]+i+X`.
- I created a lastMax that maintain the value of x for each position
- Update the array by adding index position to the corresponding element.
- Final answer will be maximum of `arr[i]+lastMax(i+1)` for `0<=i<n-1`.
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```cpp []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n= values.size();
        vector<int> lastMax(n); // at jth index store maximum of (arr[i]-i) for i>=j and i<n.
        lastMax[n-1]=values[n-1]-n+1;
        values[n-1]+=(n-1);// update by adding index to corresponding element.
        for(int i=n-2;i>=0;i--){
            lastMax[i]= max(lastMax[i+1],values[i]-i);
            values[i]+=i;
        }
        int ans=0;
        for(int i=0;i<n-1;i++){
            ans=max(ans,values[i]+lastMax[i+1]);// final answer is maximum of arr[i]+lastMax[i+1]
        }
        return ans;
    }
};
```
['C++']