class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
n = len(A)
res = 0
for i in range(n - 1):
for j in range(i + 1, n):
res = max(res, A[i] + A[j] + i - j)
return res
我们思考如何优化。 其实我们可以遍历一遍数组，对于数组的每一项A[j] - j 我们都去前面找最大的 A[i] + i （这样才能保证结果最大）。
我们考虑使用动态规划来解决, 我们使用 dp[i] 来表示 数组 A 前 i 项的A[i] + i的最大值。
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
n = len(A)
dp = [float('-inf')] * (n + 1)
res = 0
for i in range(n):
dp[i + 1] = max(dp[i], A[i] + i)
res = max(res, dp[i] + A[i] - i)
return res
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
n = len(A)
pre = A[0] + 0
res = 0
for i in range(1, n):
res = max(res, pre + A[i] - i)
pre = max(pre, A[i] + i)
return res
小技巧
Python 的代码如果不使用 max，而是使用 if else 效率目测会更高，大家可以试一下。
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
n = len(A)
pre = A[0] + 0
res = 0
for i in range(1, n):
# res = max(res, pre + A[i] - i)
# pre = max(pre, A[i] + i)
res = res if res > pre + A[i] - i else pre + A[i] - i
pre = pre if pre > A[i] + i else A[i] + i
return res
