Simple and Easy - One Pass
Start from first values. Take a variable to keep track of the maximum value which has already occured. As you move forward, with each step decrease 1 from the p
Start from first values. Take a variable to keep track of the maximum value which has already occured. As you move forward, with each step decrease 1 from the prevMax, because at every step i-j is increasing by 1. \nFind maxScore = max(maxScore, prevMax + values[i]). \nAlso, at every step update the prevMax as prevMax = max(prevMax, values[i])\n\n```\nclass Solution:\n    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n        prevMax = values[0]\n        maxScore = -inf\n        for i in range(1, len(values)):\n            prevMax -= 1\n            maxScore = max(maxScore, prevMax + values[i])\n            prevMax = max(prevMax, values[i])\n        return maxScore\n```
['Python']