You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i &lt; j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

&nbsp;
Example 1:

Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11


Example 2:

Input: values = [1,2]
Output: 2


&nbsp;
Constraints:


	2 &lt;= values.length &lt;= 5 * 104
	1 &lt;= values[i] &lt;= 1000


class Solution:
    """
    Approach: 
    O(n^2) is very straight forward
    For all the possible pairs
    for i in range(n)
      for j in range(i+1, n)
         value[i] = max(value[i], value[i] + value[j] + i - j`)
    
    we can do this problem in O(n) as well
    values = [8, 1, 5, 2, 6]
    max_val = [0, 0, 0, 0, 0]
    max_val[i] = max(max_val[i-1]-1, values[i-1]-1)
    we have to do it once from left side and then from right side
    """
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        left_max_vals = [float('-inf') for _ in range(len(values))]
        right_max_vals = [float('-inf') for _ in range(len(values))]
        
        for i in range(1, len(values)):
            left_max_vals[i] = max(left_max_vals[i-1]-1, values[i-1]-1)
            
        for i in range(len(values)-2, -1, -1):
            right_max_vals[i] = max(right_max_vals[i+1]-1, values[i+1]-1)
        
        max_pair = float('-inf')
        for i in range(len(values)):
            max_pair = max(max_pair, values[i] + max(left_max_vals[i], right_max_vals[i]))
        return max_pair
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int n=values.length;
        int[] dp=new int[n];
        dp[0]=values[0];
        int ans=0;
        for(int i=1;i<n;i++){
            dp[i]=Math.max(dp[i-1],values[i]+i);
            ans=Math.max(ans,dp[i-1]+values[i]-i);
        }
        return ans;
    }
}
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans=-1e9;
        int maxSum=values[0];
        int n=values.size();
        for(int i=1;i<n;i++){
            ans=max(ans,maxSum+values[i]-i);
            maxSum=max(maxSum,values[i]+i);
        }
        return ans;

    }
};
/**
 * @param {number[]} values
 * @return {number}
 */
var maxScoreSightseeingPair = function(values) {
    let n=values.length,
        prevIndexMaxAddition=values[n-1],
        maxValue=-2;
    for(let i=n-2;i>-1;i--){
        let curIndexMaxAddition=Math.max(values[i],prevIndexMaxAddition-1);
        let curIndexMaxValue=values[i]+prevIndexMaxAddition-1;
        if(maxValue<curIndexMaxValue){
            maxValue=curIndexMaxValue;
        }
        prevIndexMaxAddition=curIndexMaxAddition;
    }
    return maxValue;
};
Best Sightseeing Pair