LeetCode 1014. 最佳观光组合 一次遍历数组，时间复杂度O(n)
1014. 最佳观光组合
today 1014 最佳观光组合
题目描述
给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，评分由 1 到 10^6 之间的整数。
一对景点（A[i], A[j]）的观光总得分为 A[i] + A[j] + i - j，其中 i < j。
返回一对观光景点能取得的最高分。
示例
输入：[8,1,5,2,6]
输出：11
解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
输入：[1,2,3]
输出：0
解释：没有观光景点能取得更高的分数。
提示
- 1 <= A.length <= 50000
- 1 <= A[i] <= 10^6
解题思路
这道题最简单的思路是枚举所有的可能的景点对，然后计算每个景点对的得分，取最大值。但是这样会导致超时。
因此我们采用动态规划的方法,从后往前遍历数组，对于每个位置 i，我们计算 i 后续的最大分数。即ans = max(ans,values[i]+rightMax)。
其中 rightMax=max(values[i-1],rightMax-1)
复杂度分析:
- 只遍历一次数组，时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
代码实现
Python版本：
class Solution(object):
def maxScoreSightseeingPair(self, values):
ans=0
n=len(values)
rightMax=values[n-1]-1
for i in range(n-2,-1,-1):
ans=max(ans,rightMax+values[i])
rightMax=max(rightMax-1,values[i]-1)
return ans
Go版本：
func maxScoreSightseeingPair(values []int) int {
ans := 0
n := len(values)
if n == 2 {
return values[0] + values[1] - 1
}
rightMax := values[n-1]-1
for j := n - 2; j >= 0; j-- {
ans = max(ans, rightMax+values[j])
rightMax = max(rightMax-1, values[j]-1)
}
return ans
}