Greedy |  One pass | Easy Explanation | C++ 
IntuitionThe problem is to find the maximum score for a pair of indices(i,j) defined as A[i] + A[j] + i -j. This equation can be derived as -
A[i] + i (dependen
# Intuition
The problem is to find the maximum score for a pair of indices(i,j) defined as A[i] + A[j] + i -j. This equation can be derived as - 
1) A[i] + i (dependent on i)
2) A[j] - j (dependent on j)

The goal is to track the maximum value of **A[i] + i.**

# Approach
We use a map to track the maximum values of 
A[i] + i , as we iterate through the array - 
1) **Iterate** - For each index i, compute the score as max_so_far + A[i] - i , where max_so_far is the largest A[k] + k seen so far.
2) **Update Answer** - Update the maximum score using the current value
3) **Insert Values** - Add A[i] + i to the map.
# Complexity
- Time complexity:
0(NlogN)

- Space complexity:
0(N)

# Code
```cpp []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int n = A.size();
        map<int, int> mp;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!mp.empty()) {
                auto it = mp.rbegin();
                ans = max(ans, it->first + A[i] - i);
            }
            mp[A[i] + i]++; 
        }

        return ans;
    }
};
```
['Array', 'Hash Table', 'C++']