【每日一题】LeetCode 1014.最佳观光组合（数组、动态规划、枚举右维护左）

【每日一题】LeetCode 1014.最佳观光组合（数组、动态规划、枚举右维护左）

题目描述

给定一个正整数数组 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 * 10^4
• 1 <= values[i] <= 1000

思路分析

这个问题可以通过动态规划的思想来解决。我们可以维护两个变量，max 用来记录当前遍历到的景点中，能够与之前任意景点组合得到的最大分数的景点的评分加上其索引值（values[i] + i），ans 用来记录遍历过程中找到的最大组合得分。

遍历数组，对于每个景点 j，我们计算当前景点与之前所有景点 i 的组合得分，并更新 ans。同时，我们更新 max 为当前 values[j] + j，因为对于之后的任意景点 k（k > j），values[j] + j 将会是与 values[k] 组合时可能得到的最大 values[i] + i。

输入示例

• values = [8,1,5,2,6]
• values = [1,2]

代码实现

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        // 初始化 max 为第一个景点的评分加上其索引，ans 为最低分数
        int max = values[0] + 0; // values[0] + i, 当 i = 0
        int ans = 0;
        
        // 遍历数组，从第二个元素开始
        for(int j = 1; j < values.length; j++){
            // 更新 ans 为当前找到的最大组合得分
            ans = Math.max(ans, max + values[j] - j);
            // 更新 max 为当前能够与之前任意景点组合得到的最大分数的景点的评分加上其索引值
            max = Math.max(max, values[j] + j);
        }
        // 返回找到的最大组合得分
        return ans;
    }
}