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 , 0for 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