LC 1014. Best Sightseeing Pair

https://leetcode.com/problems/best-sightseeing-pair/

这题目我一开始就陷入了过去归并排序的思路。这种思路不复杂，并且时间复杂度对N<=50000应该是可以的。

我们定义两个序列： a: [A[i] + i] 和 b: [A[j] - j], 然后对a, b做归并排序。 在合并的过程中，可以看到a和b的最大值都在末尾，这样我们直接相加就好了。

另外因为A[i] <= 1000，说明我们其实不用归并长度超过1000的两个序列。 因为a的最后一个元素的下标是i, 那么b最后一个元素下标肯定>i+1000, 这样

兴致勃勃地写了觉得巨牛的程序，提交上去发现2980ms。加上长度1000这个优化也只是2492ms。 另外还有一个有趣的发现是，使用 `sorted` 直接排序比自己手写归并排序要快，可以到1168ms. 

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)
        a = [A[i] + i for i in range(n)]
        b = [A[i] - i for i in range(n)]
        MAX_SIZE = 1000

        def msort(a, b):
            assert len(a) == len(b)
            if len(a) == 1:
                return a, b

            m = len(a) // 2
            x, y = msort(a[:m], b[:m])
            w, z = msort(a[m:], b[m:])

            if len(a) >= MAX_SIZE and len(b) >= MAX_SIZE:
                return [], []

            t0, t1 = merge(x, y, w, z)
            return t0, t1

        def merge(x, y, w, z):
            # merge with x and z
            self.ans = max(self.ans, x[-1] + z[-1])

            # def f(a, b):
            #     t = []
            #     i, j = 0, 0
            #     while i < len(a) and j < len(b):
            #         if a[i] < b[j]:
            #             t.append(a[i])
            #             i += 1
            #         else:
            #             t.append(b[j])
            #             j += 1
            #     t.extend(a[i:])
            #     t.extend(b[j:])
            #     return t
            #
            # t0 = f(x, w)
            # t1 = f(y, z)
            # return t0, t1

            # 直接用sorted比手写还要快
            t0 = sorted(x + w)
            t1 = sorted(y + z)
            return t0, t1

        self.ans = 0
        msort(a, b)
        return self.ans

调整思路之后发现，对于一个点来说，我们其实就想知道在它右边的 max(A[j] - j)在哪里，没有想象的那么复杂需要使用归并排序。 

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)

        b = [A[i] - i for i in range(n)]

        for i in reversed(range(n - 1)):
            b[i] = max(b[i], b[i + 1])

        ans = 0
        p = 0
        for i in range(n - 1):
            p = max(p, A[i] + i)
            res = p + b[i + 1]
            ans = max(ans, res)
        return ans

基本上这就有动态规划的意思了。但是仔细观察的话，发现其实 `b` 这个数组也是不需要的。

在设计上面这个算法的时候，其实我是从遍历 `A[i]+i` 这个角度出发的。但如果我们考虑遍历的是 `A[j]-j` ，而如果我们可以保存过去看到的 `max(A[i]+i)` 的话，那完全不必使用到数组。 

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)

        ans = 0
        p = 0
        for i in range(1, n):
            # p always < i
            res = A[p] + p + A[i] - i
            ans = max(ans, res)
            if A[i] + i >= A[p] + p:
                p = i

        return ans