- 题目要求：
-
思路：
- 得分为 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