Using some Observation and Elementary math. [O(N) Time with O(1) Space ]
Let\'s say our current maximum answer so far is ans, now if j wants to make pair with some other element it should satisfy the following condition.\n\nans < val
Let\'s say our current maximum answer so far is **ans**, now if **j** wants to make pair with some other element it should satisfy the following condition.\n\n`ans < value[j]+value[i]-(j-i)` ---------------------------- (1)\n\nWhere **i** is the spot with which **j** will pair.\n\nIf we make some transformation in equation (1), we will get the following relation:\n\n`ans-value[j]+j < value[i]+i` -------------------------------(2)\n\nlets make a variable to track max of` value[i]+i `so far and call this variable **M_xi**;\n\nSo we can say that our ans will change only if equation (2) satisfy, our ans will change to:\n \t\t\t\t\n\t\t\tans=M_xi+value[j]-j;\n\n\nHere is the implementation of the approach.\n```\nint maxScoreSightseeingPair(vector<int>& a) {\n        int ans=a[0]+a[1]-1,M_xi=max(a[0],a[1]+1);\n        for(int i=2;i<a.size();i++){\n            if(ans-a[i]+i<M_xi){\n                ans=M_xi+a[i]-i;\n            }\n            M_xi=max(M_xi,a[i]+i);\n        }\n        return ans;\n    }\n```\n
['Dynamic Programming']