11. 观光景点组合得分问题

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐中等

问题描述

小 R 正在研究一组观光景点，每个景点都有一个评分，保存在数组 values 中，其中 values[i] 表示第 i 个观光景点的评分。同时，景点之间的距离由它们的下标差 j - i 表示。

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

小 R 想知道，在哪种情况下能够获得观光景点组合的最高得分。

约束条件：

• 2 <= values.length
• 1 <= values[i] <= 1000

测试样例

样例 1：

输入：values = [8, 3, 5, 5, 6]
输出：11

样例 2：

输入：values = [10, 4, 8, 7]
输出：16

样例 3：

输入：values = [1, 2, 3, 4, 5]
输出：8

解题思路

这道题目要求我们找到一对景点 (i, j)，其中 i < j，使得 values[i] + values[j] + i - j 的值最大。我们可以将这个公式重新整理为 (values[i] + i) + (values[j] - j)。这样，我们可以将问题分解为两部分：

1. 对于每个 j，我们需要找到 i < j 使得 values[i] + i 最大。
2. 然后计算 (values[i] + i) + (values[j] - j) 的最大值。

最优解法

我们可以使用一次遍历的方法来解决这个问题：

1. 初始化 maxScore 为负无穷，maxValuePlusI 为 values[0] + 0（即 values[0]）。
2. 从 j = 1 开始遍历数组：
   • 计算当前 j 的得分：currentScore = maxValuePlusI + values[j] - j。
   • 更新 maxScore 为 max(maxScore, currentScore)。
   • 更新 maxValuePlusI 为 max(maxValuePlusI, values[j] + j)。
3. 最后返回 maxScore。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，是最优的解法。

代码实现

function solution(values) {
    let maxScore = -Infinity;
    let maxValuePlusI = values[0] + 0; // i starts from 0
    
    for (let j = 1; j < values.length; j++) {
        // Calculate the current score
        const currentScore = maxValuePlusI + values[j] - j;
        // Update the max score
        maxScore = Math.max(maxScore, currentScore);
        // Update the max value of (values[i] + i)
        maxValuePlusI = Math.max(maxValuePlusI, values[j] + j);
    }
    
    return maxScore;
}

function main() {
    console.log(solution([8, 3, 5, 5, 6]) === 11 ? 1 : 0);
    console.log(solution([10, 4, 8, 7]) === 16 ? 1 : 0);
    console.log(solution([1, 2, 3, 4, 5]) === 8 ? 1 : 0);
}

main();

代码解释

1. 初始化：maxScore 初始化为负无穷，maxValuePlusI 初始化为 values[0] + 0（即第一个元素的值加上其索引）。
2. 遍历数组：从第二个元素开始遍历：
   • 计算当前 j 的得分 currentScore，即 maxValuePlusI + values[j] - j。
   • 更新 maxScore 为当前得分和之前最大得分的较大值。
   • 更新 maxValuePlusI 为当前 values[j] + j 和之前 maxValuePlusI 的较大值。
3. 返回结果：遍历结束后，maxScore 即为所求的最大得分。

以上关于11. 观光景点组合得分问题的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。