Leetcode 1014.最佳观光组合

题目描述

1014. 最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

输入：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

示例代码

# 时间复杂度：O(n)
# 空间复杂度: O(1)
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

// 时间复杂度：O(n)
// 空间复杂度: O(1)
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;
    }
};