Code walk through, O(n) time + O(1) space
It took me a lot of time to understand the approach explained by people in the Discussion section. \nHere\'s an example, explaning how I understood it:\nNow, gi
It took me a lot of time to understand the approach explained by people in the Discussion section. \nHere\'s an example, explaning how I understood it:\nNow, given formula for a score is\n`score = A[i] + A[j] + i - j` ; given i < j\nIt becomes more easier to group the dependant values, \ni.e `A[i] + i` and `A[j] - j`\nIn this way, when we are traversing from either sides of the array, we can just calculate that part of the score, if we maintain max of one part.\n```\nvalues = [7, 1, 6, 6, 9, 4, 3]\n```\nNow suppose I traverse the array from left to right, and decide to keep the sum `A[i] + i` maximum at each point, then I can easily use the current element value & its position to calculate the current maximum score.\nAlso, Note that at each point, we calculate `A[j] + j` and compare it to `maxLeft`, to always store the MAXIMUM of those values.\nLet\'s initialize `maxLeft = A[0] + 0 = 7`, considering `i = 0` initially. And `maxScore = 0`\n```\nwhen j = 1, \n\tscore = maxLeft + A[j] - j = 7 + 1 - 1 = 7\n\tmaxScore = max(maxScore, score) = max(0,7) = 7\n\tmaxLeft = max(maxLeft, A[j] + j) = max(7, 1+1) = 7\nwhen j = 2, \n\tscore = maxLeft + A[j] - j = 7 + 6 - 2 = 11\n\tmaxScore = max(maxScore, score) = max(7,11) = 11\n\tmaxLeft = max(maxLeft, A[j] + j) = max(7, 6+2) = 8\nwhen j = 3, \n\tscore = maxLeft + A[j] - j = 8 + 6 - 3 = 11\n\tmaxScore = max(maxScore, score) = max(11,11) = 11\n\tmaxLeft = max(maxLeft, A[j] + j) = max(8, 6+3) = 9\nwhen j = 4, \n\tscore = maxLeft + A[j] - j = 9 + 9 - 4 = 14\n\tmaxScore = max(maxScore, score) = max(11,14) = 14\n\tmaxLeft = max(maxLeft, A[j] + j) = max(9, 9+4) = 13\nwhen j = 5, \n\tscore = maxLeft + A[j] - j = 13 + 4 - 5 = 12\n\tmaxScore = max(maxScore, score) = max(14,12) = 14\n\tmaxLeft = max(maxLeft, A[j] + j) = max(13,4+5) = 13\nwhen j = 6, \n\tscore = maxLeft + A[j] - j = 13 + 3 - 6 = 10\n\tmaxScore = max(maxScore, score) = max(14,10) = 14\n\tmaxLeft = max(maxLeft, A[j] + j) = max(13, 3+6) = 13\n```\nAt the end, we return maxScore, hence our final result = 14!\n\nThe code in C++, for the same logic:\n```\n    int maxScoreSightseeingPair(vector<int>& a)\n    {\n        int n = a.size(), maxScore = 0;\n        int maxLeft = a[0] + 0;\n        for(int j = 1; j < n; j++) {\n            maxScore = max(maxScore, maxLeft + a[j] - j);\n            maxLeft = max(maxLeft, a[j] + j);\n        }\n        return maxScore;\n    }\n```\nI hope my explanation helps anyone who struggled like me!\nIf I made a mistake anywhere in my explanation, kindly let me know and i\'ll edit my post :D
['C']