C++|O(n)|Small solution with explanation
Approach\nThe prime objective of this question is to find the maximum value of the following equation,\n\nA[i] + A[j] + i - j, where i < j\n\nWe can rearrange t
# Approach\nThe prime objective of this question is to find the maximum value of the following equation,\n```\nA[i] + A[j] + i - j, where i < j\n```\nWe can rearrange this equation to take the following form,\n```\n(A[i] + i) + (A[j] - j) \n```\nNow let\'s try to optimize the above equation by fixing the value of current index, j. This comes out to be \n```\nsolution[j] = max(A[x] + x) + (A[j] - j), where x is any value less than j\n```\nIn this manner we break the solution into two parts. For the current index j, we can easily calulate the second part ,i.e, A[j] - j\nFor the first part, We need to maintain the maximum value of (A[x] + x) from the beginning to current index of this array. This can be calculated using dynamic programming, where \n```\ndp[i] = max(dp[i-1], A[i] + i) \n```\nThough this part of the solution can be optimized as we don\'t need to maintain all values of dp[i]. Instead we can use a variable that stores the current maximum value.  \n\nFinally, since we don\'t know the value of j which optimizes the equation. We take the maximum of all solution[j], where  0 < j < n. \n\nAs an additional optimization, we don\'t need to store all the solution[j] values. For this, You can refer to my solution below. \n# Solution\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int mx = values[0], ans = 0;\n        \n        for(int i=1;i<values.size();i++){\n            ans = max(ans, mx + values[i] - i);\n            mx = max(mx, values[i] + i);\n        }\n        \n        return ans;\n    }\n};\n```\n# Complexity #\nSpace complexity - O(1)\nTime complexity - O(n)
['Math', 'Dynamic Programming', 'C']