Code with thought process
The first obvious thing in the problem is that it is very easy to brute force it in O(n^2) To do better than that you can try nlogn but for that you will need a
The first obvious thing in the problem is that it is very easy to brute force it in O(n^2) To do better than that you can try nlogn but for that you will need a log term which can some from sorting etc but order is important in this problem , so thats probably not possible which leaves us with O(n)\n\nFor the problem to be O(n) it implies that for every step in the brute force process when you are comparing each number with every other number there is a way to avoid all those computations making each step O(1) for the n numbers. So when looking at a pair of numbers at each step we must know exactly which number in the pair to reject for all future comparisons. So lets assume thats true and see if we can indeed do that at every step\n\nLets start with two numbers A[0] and A[1]\n\nIf A[0] <= A[1] then we can reject A[0] because every pair that A[0] will be involved in A[1] can do better in them since A[1] is bigger and closer to other numbers\n\nThe other case A[0] > A[1]. In this case we can safely reject A[1] for all future comparisons because A[0] will at least as good as A[1] for all those comparisons because A[1] is 1 closer to other numbers but A[0] is at least 1 bigger than A[1] (since the numbers are integers)\n\nSo each step we know exactly which number to reject in the current pair. This line of thinking is useful in many array problems. \nAs a trick in the code to keep track of which numbers are being compared currently I always keep them adjacent to each other by swapping when necessary and decrementing value to account for change in index\n\n```\n    def maxScoreSightseeingPair(self, A: List[int]) -> int:\n        \n        \n        best_score = 0\n        n = len(A)\n        i = 0\n        j = 1 # Dont need j but I have kept it for readabililty\n        \n        while i < n and j < n:\n            \n            score = A[i] + A[j] + i - j\n            best_score = max(score, best_score)\n            \n            if A[i] > A[j]:\n                A[i] -= 1\n                A[i], A[j] = A[j], A[i]\n                \n            i += 1\n            j += 1\n        \n        return best_score\n        \n```
[]