数组题目：最佳观光组合

本文主要是介绍数组题目：最佳观光组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

标题和出处

标题：最佳观光组合

出处：1014. 最佳观光组合

难度

4 级

题目描述

要求

给定正整数数组 $\text{values}$，$\text{values[i]}$ 表示第 $\text{i}$ 个观光景点的评分，并且两个景点 $\text{i}$ 和 $\text{j}$ 之间的距离为 $\text{j - i}$。

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

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

示例

示例 1：

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

示例 2：

输入：$\text{values = [1,2]}$
输出：$\text{2}$

数据范围

• $\text{2}\le \text{values.length}\le \text{5}\times {\text{10}}^{\text{4}}$
• $\text{1}\le \text{values[i]}\le \text{1000}$

解法

思路和算法

假设数组 $\text{values}$ 的长度是 $n$。最直观的做法是遍历每一对下标 $(i,j)$，其中 $0\le i<j<n$，计算观光组合得分，时间复杂度是 $O(n^2)$，会超出时间限制，因此必须优化。

当 $i<j$ 时，将景点对 $(i,j)$ 组成的观光组合的得分记为 $f(i,j)$，则有：

$$f(i,j)=\text{values}[i]+\text{values}[j]+i-j$$

是否可以优化 $f(i,j)$ 的计算呢？注意到 $f(i,j)$ 可以写成如下形式：

$$f(i,j)=\text{values}[i]+i+\text{values}[j]-j(i<j)$$

记 $g(i)=\text{values}[i]+i$，$h(j)=\text{values}[j]-j$，则有：

$$f(i,j)=g(i)+h(j)(i<j)$$

由此可以想到优化的做法：遍历数组 $\text{values}$，遍历过程中维护最大的 $g$ 的值，根据最大的 $g$ 的值和当前的 $h(j)$ 的值计算观光组合的最高得分。

具体实现方面，维护 $\text{leftMax}$ 为最大的 $g$ 的值，初始时 $\text{leftMax}=\text{values}[0]+0=\text{values}[0]$。从左到右遍历数组 $\text{values}$，对于 $1\le i<n$，计算 $h(i)$ 的值，使用 $\text{leftMax}+h(i)$ 更新观光组合的最高得分，然后用 $g(i)$ 更新 $\text{leftMax}$ 的值。

上述两步操作的顺序不能颠倒，必须先更新观光组合的最高得分，后更新 $\text{leftMax}$ 的值，因为观光组合必须是两个不同的景点的组合。

代码

class Solution {public int maxScoreSightseeingPair(int[] values) {int maxScore = 0;int leftMax = values[0];int length = values.length;for (int i = 1; i < length; i++) {int right = values[i] - i;maxScore = Math.max(maxScore, leftMax + right);leftMax = Math.max(leftMax, values[i] + i);}return maxScore;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{values}$ 的长度。需要遍历数组 $\text{values}$ 一次，对每个下标位置计算最大评分之和的时间复杂度是 $O(1)$，因此总时间复杂度是 $O(n)$。

• 空间复杂度：$O(1)$。

这篇关于数组题目：最佳观光组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---