✅ || Very easy explanation ||  DP || Complexity Analysis || Python
Solution\n\n\n#### LOGIC\n\nSuppose we have a = [8,1,5,2,6]\ncreate a dp = [0, 0, 0, 0] where dp[i] represents the best possible answer if we consider all pairs
## **Solution**\n\n\n#### **LOGIC**\n\nSuppose we have a = ```[8,1,5,2,6]```\ncreate a dp = ```[0, 0, 0, 0]``` where dp[i] represents the best possible answer if we consider all pairs forming with a[i] (like i = 3 then it will be (0, 3),(1, 3), (2, 3))\n\n* For d[0] it will be 0\n* For d[1] it will be a[0] + a[1] + 0 - 1\n* For d[2] it will be max((a[0] + a[2] + 0 - 2), (a[1] + a[2] + 1 - 2))\n* For d[3] it will be max((a[0] + a[3] + 0 - 3), (a[1] + a[3] + 1 - 3), (a[2] + a[3] + 2 - 3))\n* For d[4] it will be max(a[0] + a[4] + 0 - 4), (a[1] + a[4] + 1 - 4), (a[2] + a[4] + 2 - 4), (a[3] + a[4] + 3 - 4))\n\nRewriting above by taking about common term out of max() function\n* For d[0] it will be 0\n* For d[1] it will be a[0] + 0 + a[1] - 1\n* For d[2] it will be max((a[0] + 0), (a[1] + 1)) + a[2] - 2\n* For d[3] it will be max((a[0] + 0 ), (a[1] + 1), (a[2] + 2)) + a[3] - 3\n* For d[4] it will be max(a[0] + 0 ), (a[1] + 1), (a[2] + 2), (a[3] + 3 )) + a[4] - 4\n\nFor a minute lets ignore the part outside the max function and drop it for now, So make a new series and call it dp\n* For dp[0] it will be 0\n* For dp[1] it will be a[0] + 0\n* For dp[2] it will be max((a[0] + 0), (a[1] + 1))\n* For dp[3] it will be max((a[0] + 0 ), (a[1] + 1), (a[2] + 2))\n* For dp[4] it will be max(a[0] + 0 ), (a[1] + 1), (a[2] + 2), (a[3] + 3 ))\n\n**Here is the catch\ndp[i] = max(dp[i-1], a[i-1] + i - 1)\nYou can Clearly see this pattern in above dp series**\n\nCombining this to d series we can get:\n* For d[0] it will be 0\n* For d[1] it will be dp[0]+ a[1] - 1\n* For d[2] it will be max(dp[1], (a[1] + 1)) + a[2] - 2\n* For d[3] it will be max(dp[2], (a[2] + 2)) + a[3] - 3\n* For d[4] it will be max(dp[3], (a[3] + 3 )) + a[4] - 4\n\n**Now our answer can simply the maximum of d that is max(d), but for improving space complexity i used maxVal to keep track of maximum value**\n\n#### **Code**\n\n##### Apporach : 1  \n```cpp\nclass Solution:\n    def maxScoreSightseeingPair(self, values: List[int]) -> int:      \n      dp = [0]*(len(values))\n      dp[0] = values[0]\n      maxVal = 0\n      \n      for i in range(1, len(values)):\n        dp[i] = max(dp[i-1], values[i-1]+i-1)\n        maxVal = max(maxVal, dp[i]+values[i]-i)\n      \n      return maxVal\n```\n\n##### Apporach : 2[Memory Efficient]\n```cpp\nclass Solution:\n\n    def maxScoreSightseeingPair(self, values: List[int]) -> int:    \n      maxVal = 0\n      cur = 0            \n      for i in range(1, len(values)):\n        cur = max(cur, values[i-1]+i-1)\n        maxVal = max(maxVal, cur+values[i]-i)\n      return maxVal\n\n```\n## **Complexity**\n\n##### __Apporach : 1__  \n##### Time Complexity:  **O(n)**.\n\n##### Space Complexity: **O(n)**\n\n##### __Apporach : 2__  \n##### Time Complexity:  **O(n)**.\n\n##### Space Complexity: **O(1)**\n<br>\n\n __Check out all [my](https://leetcode.com/siddp6/) recent solutions [here](https://github.com/sidd6p/LeetCode)__\n\n \n __Feel Free to Ask Doubts\nAnd Please Share Some Suggestions\nHAPPY CODING :)__\n\n\n
['Dynamic Programming', 'Python', 'Python3']