Leetcode1014-最佳观光组合-Python实现

• 题目要求：

• 思路：

  • 得分为 A[i] + A[j] + i – j，可以分为 (A[i] + i) 和(A[j] – j)，最高分为两个之和
  • 所以遍历数组，维护两个值，一个是 A[i] + i 的最大值，另一个是 A[i] + i + A[j] – j 的最大值
  • 第二个值维护的不是 A[j] – j 的最大值是因为最大值还与 i – j 有关，所以要根据 i – j 保存最大值
• 核心代码：

res , localmax = 0 , 0
for index , value in enumerate(A):
    # 先保存全局的结果，因为 localmax 保存的是 A[i] + i，如果先改变 localmax，说明当前的 A[i] - i 最大，那么 res 就变成 A[i] + i + A[i] - i，没有意义了
    res = max(res, localmax - index + value)
    localmax = max(localmax, index + value)
return res

• 完整代码：

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res , localmax = 0 , 0
        for index , value in enumerate(A):
            res = max(res, localmax - index + value)
            localmax = max(localmax, index + value)
        return res 

• 直观一些：

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res, localmax = 0, 0
        for i in range(len(A)):
            res = max(res, localmax - i + A[i])
            localmax = max(localmax, A[i] + i)
        return res

• 更直观：

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res, localmax = 0, 0
        for i in range(len(A)):
            j = i
            res = max(res, localmax + A[j] - j)
            localmax = max(localmax, A[i] + i)
        return res