Simple DP || Beats 100% || Linear Time || No Extra Space
IntuitionIf we calculate the score using the value at index i with value at index x and x+1 (i<x), keeping the value at later indices (x and x+1) as it is, the
![Screenshot 2024-12-27 163318.png](https://assets.leetcode.com/users/images/528d05f4-6108-404d-96bb-d4645adbdf02_1735297880.8239794.png)

# Intuition
If we calculate the score using the value at index i with value at index x and x+1 (i<x), keeping the value at later indices (x and x+1) as it is, the value contributed by number at index i will be one lesser when calculated with index x+1 (arr[x+1] + arr[i]+i-x -1) compared to index x (arr[x] + arr[i]+i-x). So we can see that with each increasing index the sum contributed by previous values is getting reduced by one. We can use a varibale to store the best contribution previous elements can give to the score and add it with elements at each index to get the maximum sum till that index. After last index, we will get the score of the best pair.

# Approach
1. Use a ***curr*** variable to store maximum any previous value can contribute to the sum. Initialize it with value 0.
2. Initialize the ***ans*** variable with 0. It will store the best sum of best pair.
3. Iterate through the vector/list and at each index add the curr variable to see if exceeds the maximum score stored in ans.
4. Also, notice that the impact ***curr*** varible to the score will decrease by one for the next index. Also, if the value at present index is greater than ***curr***, we will replace ***curr*** with present value.
**Note:** The assigning of ***curr*** as maximum of ***curr*** and present value as well as decreasing the ***curr*** value has been done at single step in the solution given.
5. Return the ***ans*** variable as it contains the maximum score of the best pair.

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(1)$$

# Code
```python3 []
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        curr,ans=0,0
        for i in values:
            ans=max(ans,i+curr)
            curr=max(curr-1,i-1)
        return ans
```
```C++ []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans=0,curr=0;
        for(int i: values) {
            ans=max(ans,i+curr);
            curr=max(curr-1,i-1);
        }
        return ans;
    }
};
```

# Please provide any necessary feedback and give me an upvote if you liked my explanation. Thanks.


['Array', 'Dynamic Programming', 'C++', 'Python3']