Detailed Explanation using DP [O(n) Time | O(1) Space]
Intuition\n Suppose we choose the site [i,...j]. The score can be broken up into 2 parts.\n The first part is the startGain which you gain while starting at a c
**Intuition**\n* Suppose we choose the site `[i,...j]`. The score can be broken up into 2 parts.\n* The first part is the **startGain** which you gain while starting at a certain point `i`. Notice that `startGain[i] = a[i] + i`.\n* The second part is the **endGain** which is the amount you gain while ending at a certain point `j`. Notice that `endGain[i] = a[j] - j`.\n* Notice that endGain can be negative\n* The overall gain for `[i,...j]` is nothing but `startGain[i] + endGain[j]`. (This can be easily verified by the definitions).\n---\n**Constraints**\n* You cannot start at the last position\n* You cannot go left at any stage, i.e if you started at `i`, you have to end your trip at a number **strictly** bigger than `i`.\n---\n**Reduction**\n* We need to maximize the overall Gain.\n---\n\n* What are the possible positions for starting the trip? Clearly we can start at all except the last element. So, the optimal trip has to start at one of these elements.\n* Suppose, we are only allowed to start a trip at `i`. What is the maximum amount we can gain in this case? Well, since the `startGain` is fixed, we need to maximize the\n`endGain`. We can do it by stopping at an element which has the maximum `endGain` with the condition that it appears to the right of `i`.\n---\n**Setting up the DP definition**\n* As discussed above, for each i, we need to find the maximum `endGain` to the right of it. \n* `maxEndRight[i] = max(maxEndRight[i+1], endGain[i+1])` = `max(maxEndRight[i+1], a[i+1] - (i+1))`\n* `maxEndRight[i]` represent the highest `endGain` that you can get while stopping at any point **strictly** to the right of `i`. Since by definition, we already know `endGain[i+1]` (the highest gain possible by ending at any point to the right of `i+1`) we only need to check the possibility whether stopping at `i+1` would be beneficial or not. Hence, the DP definition.\n* For each valid `i`, `overallGain[i] = startGain[i] + maxEndRight[i]` = `a[i] + i + maxEndRight[i]`\n---\n**Reducing the Space complexity**\n* Notice that `maxEndRight[i]` only depends on `maxEndRight[i+1]`. Hence, we can use 2 variables to track the previous values.\n---\n**Miscellaneous**\n* Since we need the value of `maxEndRight[i+1]` to compute the value of `maxEndRight[i]`, therefore we start the iterations at the back.\n* As argued, trips cannot start at the last element, hence the `for` loop starts at `i=n-2`. For this value, `maxEndingRight` is initialized to `endGain[lastIndex]` because this is the only possible way to end the trip.\n```\nclass Solution\n{\npublic:\n    int maxScoreSightseeingPair(vector<int>& a);\n};\n\nint Solution :: maxScoreSightseeingPair(vector<int>& a)\n{\n    int n = a.size();\n    int maxOverallGain = INT_MIN;\n    int maxEndRight = a[n-1] - (n-1);\n    for(int i=n-2; i>=0; i--)\n    {\n        maxEndRight = max(maxEndRight, a[i+1] - (i+1));\n        maxOverallGain = max(maxOverallGain, a[i] + i + maxEndRight);\n    }\n    return maxOverallGain;\n    \n}\n```
[]