Simple O(n) C++ DP Solution || Space Optimized DP
Intuition & Logic :\nWe have the formula score = values[i] + values[j] +i -j\nNow, we are required to maximise score. So, we can modify the the formula as:\nmax
**Intuition & Logic :**\nWe have the formula score = values[i] + values[j] +i -j\nNow, we are required to maximise score. So, we can modify the the formula as:\nmax(score) = max(values[i] + values[j] + i - j) = max(values[i]+i) + max(values[j] - j)\n\nNow, at every index j, values[j]-j is fixed. Hence our obejctive would be to find the best previous index(i) which gives us the maximum score. We will achieve this by storing the values in a dp array, by calculating the max value between the previously stored value and current calculated value, i.e values[i] + i.\n\nFinally, we will calculate score based on our formula, where max(values[i]+i) will be stored in dp[i-1].\n\nThe **code** is given below : \n\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int score=INT_MIN,n=values.size();\n        int dp[n];\n        dp[0]=values[0];\n        \n        for(int i=1;i<n;i++){ \n            score=max(score,dp[i-1]+values[i]-i);\t\t\n            dp[i] = max(dp[i-1],values[i]+i);\n        }\n        \n        return score;\n    }\n};\n```\n\nTime Complexity : O(n)\nSpace Complexity: O(n)\n\nNow, we can reduce the extra space by storing the  max(values[i]+i) in a variable instead of an array.\n\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int score=INT_MIN,n=values.size();\n        int maxLeft = values[0];\n        \n        for(int i=1;i<n;i++){ \n            score=max(score,maxLeft+values[i]-i);\n            maxLeft = max(maxLeft,values[i]+i);\n        }\n        \n        return score;\n    }\n};\n```\n\nT.C: O(n)\nS.C: O(1)\n\n**Please upvote if you liked the explanation**
['Dynamic Programming', 'C', 'C++']