✅Python 3 | O(n) | Very clearly explained!
Solution 1: Brute Force [Time Limit Exceeded]\nThe most naive solution is that we can have a brute force solution by simply getting all possible combinations of
***Solution 1: Brute Force [Time Limit Exceeded]***\nThe most naive solution is that we can have a brute force solution by simply getting all possible combinations of index `i` and `j`, and then finding the maximum of `values[i] + values[j] + i - j` when `i < j` for all combinations and that will be our answer. We can do this by using a 2 nested for loops keeping track of index `i` and index `j`, while skipping to the next iteration if `i >= j`. We initialize a variable `maximum` and each iteration we check to see if the current value is higher than maximum, if so, we set maximum to this new value. Returning `maximum` in the end will give us our answer.\n```\nclass Solution:\n    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n        n = len(values)\n        maximum = 0\n        for i in range(n):\n            for j in range(i+1, n):\n                if i >= j: continue\n                maximum = max(maximum, values[i] + values[j] + i - j)\n        return maximum\n```\nTime Complexity: O(n^2)\nSpace Complexity: O(1)\n\n***Solution 2: One Pass***\n\n**Intuition**\nNotice how in the brute force solution, we skip to the next iteration if index `i >= j`. Although we skip to the next iteration using `continue`, we still iterated through many unnecessary iterations giving us a slow O(n^2) time complexity which exceeded the time limit. Thus, we can simply skip all the unnecessary iterations where `i >= j` altogether using this one pass algorithm.\n\n**Algorithm**\nWe can initialize `i` to be 0, and then this time we only need to start 1 for loop tracking the index `j`, same thing as the brute force solution, we keep track of a variable `maximum` and in the iteration if `values[i] + values[j] + i - j` is bigger than the current `maximum` we replace it with that. However, one thing we are doing differently is that instead of starting a nested for loop we write an if statement saying that `values[j] + j - i > values[i]` then we set `i=j`. Basically, you can treat `if values[j] + j - i > values[i]: i = j` the same thing as `if i >= j: continue` in the brute force solution, except we are not iterating unnecessarily.\n\n**Implementation**\n```\nclass Solution:\n    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n        n = len(values)\n        i = maximum = 0\n        for j in range(i+1, n):\n            maximum = max(maximum, values[i] + values[j] + i - j)\n            if values[j] + j - i > values[i]: i = j\n        return maximum\n```\nTime Complexity: O(n)\nSpace Complexity: O(1)\n\n**Please consider upvoting if this solution helped you. Good luck!**\n\n
['Python', 'Python3']