class Solution {
public:
    int omax = 0, ans= 0;
    int maxScoreSightseeingPair(vector<int>& values) {
        int maxi = 0;
        int n = values.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));  
        
        for(int i= 0, j = 1; i<values.size()-1;i++){
            
            maxi = max(maxi,dp1(values,i, j, dp));
        }
        
        return maxi;
    }
    
    int dp1(vector<int>& values, int i, int j,vector<vector<int>>& dp){
        if(j > values.size()-1){
            return 0;
        }
        
        if(dp[i][j] != -1){
            return dp[i][j];
        }
        
        int cur = values[i]+values[j] + i-j;
        omax = max(cur, dp1(values,i,j+1,dp));
        return max(ans, omax);
    }
};