C++, Dynamic Programming, O(N) time, simple with explanation
Since our task is to find max{ (A[i]+i) + (A[j]-j) } for all i<j.\nSo we can say that we want maximum of A[i]+i and maximum of A[j]-j.\nUsing Dynamic Programmin
Since our task is to find ``max{ (A[i]+i) + (A[j]-j) }`` for all ``i<j``.\nSo we can say that we want maximum of ``A[i]+i`` and maximum of ``A[j]-j``.\n**Using Dynamic Programming**\ntime complexity: O(N)\nspace complexity: O(N)\n\nSubproblem: find max ``(A[i]-i)`` after ``i``.\nRecurrence Relation: ``max_after(i) = max{ A[i]-i, max_after(i+1) }``.\nFinally ans would be maximum of ``A[i]+i+max_after(i+1)``.\n```\nclass Solution {\npublic:       \n    int maxScoreSightseeingPair(vector<int>& A) {\n        int N = A.size();\n        vector<int> max_after(N,0);\n        max_after[N-1] = A[N-1] - (N-1);\n        for(int i=N-2;i>=0;i--)\n            max_after[i] = max(max_after[i+1],A[i]-i);\n        int ans = 0;\n        for(int i=0;i<N-1;i++)\n            ans = max(ans, A[i]+i+max_after[i+1]);\n        return ans;\n    }\n};\n```\n\n**Without Extra space**\ntime complexity: O(N)\nspace complexity: O(1)\n\nActually we are optimizing above algorithm.\nWe see in first for loop ``max_after[i]`` is dependent on ``max_after[i+1]`` and its current element diff.\nInstead we can use a variable to store previous ``max_after`` to calculate ``ans``;\n```\nclass Solution {\npublic:       \n    int maxScoreSightseeingPair(vector<int>& A) {\n        int N = A.size();\n        int ans = 0;\n        int max_after = A[N-1]-N+1;\n        for(int i=N-2;i>=0;i--){\n            max_after = max(max_after, A[i+1]-i-1);\n            ans = max(ans, A[i]+i+max_after);\n        }\n        return ans;\n    }\n};\n```\n\npardon my English.\nHappy Coding!
['Dynamic Programming', 'C']