Leetcode.1014 最佳观光组合

题目链接

Leetcode.1014 最佳观光组合 Rating ： 1730

题目描述

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

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

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

示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

输入：values = [1,2]
输出：2

提示：

• $2<=values.length<=5\ast 10^4$
• $1<=values[i]<=1000$

解法：动态规划

首先我们将这个式子 values[i] + values[j] + i - j 看成两部分 values[i] + i和 values[j] - j，我们就是要让这两部分加起来最大。

我们用 left来表示 [0,j-1]中最大的 values[i] + i，那么原式转换为求 left + values[j] - j的最大值，直接一次遍历即可。

时间复杂度：$O(n)$

C++代码：

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0 , left = values[0];
        int n = values.size();

        for(int i = 1;i < n;i++){
            ans = max(ans,left + values[i] - i);
            left = max(left,values[i] + i);
        }
        return ans;
    }
};

Python代码：

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        ans , left = 0 , values[0]
        n = len(values)

        for i in range(1,n):
            ans = max(ans , left + values[i] - i)
            left = max(left , values[i] + i)

        return ans