C++ O(n) solution
A[i] + A[j] + i - j  = (A[i] + i ) + (A[j]  - j)\nWhen we iterate the array A, (A[j] - j )is known.\nFor each index j, to make (A[i] + i) + (A[j]  - j) maximum,
A[i] + A[j] + i - j  = (A[i] + i ) + (A[j]  - j)\nWhen we iterate the array A, (A[j] - j )is known.\nFor each index j, to make (A[i] + i) + (A[j]  - j) maximum,  we need to find the index i such that A[i] + i  is maximum. We can record the value that gives us the max A[i] + i .\n```\nclass Solution {\npublic:\n    int maxScoreSightseeingPair(vector<int>& A) {\n        int maxScore = 0;\n        int max_AiPlusi = A[0] + 0;\n        for(int j = 1; j < A.size(); j++)\n        {\n            maxScore = max(maxScore, max_AiPlusi + A[j] - j);\n            max_AiPlusi = max(max_AiPlusi, A[j] + j);\n        }\n        return maxScore;\n    }\n};\n```
[]