Leetcode 1014.最佳观光组合
题目描述
给你一个正整数数组 values,其中 values[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点(i < j)组成的观光组合的得分为 values[i] + values[j] + i - j ,也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
1 2 3
| 输入:values = [8,1,5,2,6] 输出:11 解释:i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
|
解题思路
本题和股票买卖1类似 具体可以参考股票1的代码
就是加了个ij上去而已
因此我们可以用两个变量去维护状态
一个更新目前的最大值
一个更新values[i]+i
示例代码
1 2 3 4 5 6 7 8 9 10
|
class Solution: def maxScoreSightseeingPair(self, values: List[int]) -> int:
a,b = 0,values[0]+0 for i in range(1,len(values)): a = max(a,b+values[i]-i) b = max(b,values[i]+i) return a
|
1 2 3 4 5 6 7 8 9 10 11 12 13
|
class Solution { public: int maxScoreSightseeingPair(vector<int>& values) { int i = 0, j = values[0]; for(int w = 1; w < values.size(); w++){ i = max(i,j+values[w]-w); j = max(j,values[w]+w); } return i; } };
|
