C++, O(n) time, O(1) space, single pass with explantion.
Consider the f(n) that needs to be maximised here, which we need to maximise the sum of two values (with the difference between their places), ie.\nf(n) = maxim
Consider the f(n) that needs to be maximised here, which we need to maximise the sum of two values (with the difference between their places), ie.\nf(n) = maximize(value[i] + value[j] + j - i) where, j > i\n\nFor sometime, lets forget about the j-i part. So, how would you solve the problem if you were just to maximize the sum of two values? You could simply do this by keeping track of the maximum value you have seen so far, and while iterating over the array add the maximum to the current value, and see if this is the greatest result so far, and keep updating the maximum value too while iterating. The key observation here is that, if you have seen a large number while iterating, all numbers smaller than the number become useless to form the pair.\n\nNow, if we come to the question at hand, the only change is that we need to subtract the distance between the two numbers (j-i). So, instead of seeing it as the distance, you could just subtract this distance from the maximum value you have seen. In a way, the maximum value you have seen decays be 1, every time you move one step right. \n\nUsing this, you can solve the question in O(n) time, and O(1) space, and one pass.\n\nFor more help on competitive programming, join the discord here: \nhttps://discord.gg/aybzamxHWX\n\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& values) {\n        // Stores the maximum score to return.\n        int maxScore = 0;\n        \n        // Stores the maximum value seen until now.\n        int maxValue = 0;\n        \n        for(int i=0; i<values.size(); i++) {\n            // Since we move one place to the right, the maximum value\n            // that can form the pair decays by 1. This is to account\n            // for the distance between the current number and the maximum\n            // number.\n            maxValue = maxValue-1;\n            \n            // Update the max score, if the current number can form\n            // a better pair with the maximum number.\n            maxScore = max(maxScore, maxValue + values[i]);\n            \n            // update the maximum number seen so far.\n            if(values[i] > maxValue) {\n                maxValue = values[i];\n            }\n        }\n        \n        return maxScore;\n    }\n};\n```
[]