An intuitive way to think about the problem (o(n) time+o(1) space )
The key point of the question is to get a pair of (i,j) that A[i]+A[j]+i-j is max. \nLet\'s reformat the function to (A[i]+i)+(A[j]-j). So it is clear that when
The key point of the question is to get a pair of `(i,j)` that `A[i]+A[j]+i-j` is max. \nLet\'s reformat the function to `(A[i]+i)+(A[j]-j)`. So it is clear that when reaching index `j`, we want to \n1. find the maximum value of `(A[i]+i)` from `0` to `j-1`;\n2. calculate the sum of previous maximum value and `A[j]-j`.\n\nSo a clear DP solution is:\n\n```\nclass Solution:\n    def maxScoreSightseeingPair(self, A: List[int]) -> int:\n        prev_max = A[0]\n        res = 0\n        for j in range(1, len(A)):\n            res = max(prev_max+A[j]-j, res)\n            prev_max = max(prev_max, A[j]+j)\n        return res\n```
[]