Python one pass O(N) this is not a dp problem
I think this is more a two pointer problem than DP.\nmax value is "values[i] + values[j] + i - j", just split to two part "values[i] + i" and "values[j] - j". W
I think this is more a two pointer problem than DP.\nmax value is "values[i] + values[j] + i - j", just split to two part "values[i] + i" and "values[j] - j". When iterate over the array, remember that max value of value[i] + i.\n\n```\nclass Solution:\n    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n        maxPrev = values[0] + 0  # maxPrev, records max value of values[i] + i\n        ans = 0  # ans, the result of max value "values[i] + values[j] + i - j"\n        for i in range(1, len(values)):\n            secPart = values[i] - i\n            ans = max(ans, maxPrev + secPart)\n            maxPrev = max(maxPrev, values[i] + i)\n        return ans\n```
[]