Java O(N) Easy to Understand, Clean Code beats 100%
We want to maximize A[i] + A[j] + i - j where j > i, meaning i is to the left and j is to the right\n1. One way to think about this is that we somehow make sure
We want to maximize `A[i] + A[j] + i - j` where `j > i`, meaning `i` is to the left and `j` is to the right\n1. One way to think about this is that we somehow make sure that we add the best value of `A[i] + i` to `A[j] - j` as we go from left to right. So, at any point, while going towards right end, we add the best value available to the left.\n```\npublic int maxScoreSightseeingPair(int[] A) {   \n        int i=0;\n\t\tint max = A[i] + i;\n        for(int j=1;j<A.length;j++){\n            int curr = A[i] + A[j] + i - j;\n            max = curr > max ? curr : max;\n            \n            // update the value of i to the one that maximizes\n            if(A[i] + i < A[j] + j){\n                i=j;\n            }\n        }\n        return max;\n    }\n```\n2. Other way to think is to make sure we add the best value of `A[j]-j` to `A[i] + i` as we go from right to left. So, at any point, while going towards left end, we add the best value available to the right.\n\n```\npublic int maxScoreSightseeingPair(int[] A) {\n        int N = A.length;\n\t\tint j=N-1;\n        int max = A[j] - j;\n        for(int i=N-2;i>=0; i--){\n            int curr = A[i] + A[j] + i - j;\n            max = curr > max ? curr : max;\n            \n            // update the value of j to the one that maximizes\n            if(A[j] - j < A[i] - i){\n                j=i;\n            }\n        }\n        return max;\n    }\n```
[]