LeetCode 1014中等DP/前缀最值
最佳观光组合 图解题解
这道题到底在问什么
给定数组 values，values[i] 是第 i 个景点评分。对 i < j，组合得分 = values[i] + values[j] + i − j。返回最大得分。
- 输入
- values=[8,1,5,2,6]
- 输出
- 11 （选 i=0、j=2：8+5+0−2=11）
最优解：一步一步想明白
- 3记住「拆成 (values[i]+i)+(values[j]−j)，扫 j 维护左边最大的 values[i]+i」，下面每帧都在套它。
- 4开局把第 0 个景点作为左端候选：bestLeft = values[0]+0 = 8（绿色标出当前最佳左端）。从 j=1 开始，每个 j 都拿 bestLeft 来配对。
- 5右端点走到第 1 个（评分 1）。配上左边最佳端点（绿色，下标 0）：得分 8 + 1 − 1 = 8。比旧的最大得分更高，刷新 ans=8。
- 6第 1 个作为左端候选只有 values[1]+1 = 2，没超过 bestLeft=8，最佳左端不动，绿色仍停在下标 0。
- 7右端点走到第 2 个（评分 5）。配上左边最佳端点（绿色，下标 0）：得分 8 + 5 − 2 = 11。比旧的最大得分更高，刷新 ans=11。
- 8第 2 个作为左端候选只有 values[2]+2 = 7，没超过 bestLeft=8，最佳左端不动，绿色仍停在下标 0。
- 9右端点走到第 3 个（评分 2）。配上左边最佳端点（绿色，下标 0）：得分 8 + 2 − 3 = 7。没超过当前最大 ans=11，保持。
- 10第 3 个作为左端候选只有 values[3]+3 = 5，没超过 bestLeft=8，最佳左端不动，绿色仍停在下标 0。
- 11右端点走到第 4 个（评分 6）。配上左边最佳端点（绿色，下标 0）：得分 8 + 6 − 4 = 10。没超过当前最大 ans=11，保持。
- 12再把第 4 个也纳入「左端候选」：values[4]+4 = 10，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 4，bestLeft=10。后面的 j 会用这个更优的左端。
- 13右端点走到第 5 个（评分 7）。配上左边最佳端点（绿色，下标 4）：得分 10 + 7 − 5 = 12。比旧的最大得分更高，刷新 ans=12。
- 14再把第 5 个也纳入「左端候选」：values[5]+5 = 12，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 5，bestLeft=12。后面的 j 会用这个更优的左端。
- 15右端点走到第 6 个（评分 3）。配上左边最佳端点（绿色，下标 5）：得分 12 + 3 − 6 = 9。没超过当前最大 ans=12，保持。
- 16第 6 个作为左端候选只有 values[6]+6 = 9，没超过 bestLeft=12，最佳左端不动，绿色仍停在下标 5。
- 17右端点走到第 7 个（评分 9）。配上左边最佳端点（绿色，下标 5）：得分 12 + 9 − 7 = 14。比旧的最大得分更高，刷新 ans=14。
- 18再把第 7 个也纳入「左端候选」：values[7]+7 = 16，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 7，bestLeft=16。后面的 j 会用这个更优的左端。
- 19右端点走到第 8 个（评分 4）。配上左边最佳端点（绿色，下标 7）：得分 16 + 4 − 8 = 12。没超过当前最大 ans=14，保持。
- 20第 8 个作为左端候选只有 values[8]+8 = 12，没超过 bestLeft=16，最佳左端不动，绿色仍停在下标 7。
- 21右端点走到第 9 个（评分 10）。配上左边最佳端点（绿色，下标 7）：得分 16 + 10 − 9 = 17。比旧的最大得分更高，刷新 ans=17。
- 22再把第 9 个也纳入「左端候选」：values[9]+9 = 19，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 9，bestLeft=19。后面的 j 会用这个更优的左端。
- 23扫完全程，最优是绿色这一对：下标 7（评分 9）和下标 9（评分 10），得分 9+10+7−9 = 17。一遍扫描、不回头就锁定了答案。
⚠️ 容易写错的地方
✗ 错：先更新 bestLeft 再结算 ans
✓ 对：必须先结算 ans 再更新 bestLeft
反了会把 i=j 也算进去，违反 i < j
✗ 错：把公式当成不可拆的整体去枚举点对
✓ 对：拆成 (values[i]+i)+(values[j]−j) 解耦
解耦后右端只需左边的前缀最大值，O(n) 即可
✗ 错：ans 初始化为 0
✓ 对：ans 初始化为极小值
得分可能很小甚至为负，用 0 会漏掉真实最大
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
best_left = values[0]
ans = -10**18
for j in range(1, len(values)):
ans = max(ans, best_left + values[j] - j)
best_left = max(best_left, values[j] + j)
return ansC++
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int bestLeft = values[0], ans = INT_MIN;
for (int j = 1; j < (int)values.size(); ++j) {
ans = max(ans, bestLeft + values[j] - j);
bestLeft = max(bestLeft, values[j] + j);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int bestLeft = values[0], ans = Integer.MIN_VALUE;
for (int j = 1; j < values.length; j++) {
ans = Math.max(ans, bestLeft + values[j] - j);
bestLeft = Math.max(bestLeft, values[j] + j);
}
return ans;
}
}复杂度
时间
O(n)
只扫一遍
空间
O(1)
只用 bestLeft、ans 两个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最佳观光组合 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题和「买卖股票 LC121」像在哪？+
都是「固定右端点、维护左边某个前缀最优」的一遍扫描。LC121 维护的是左边历史最低价，本题维护的是左边最大的 values[i]+i。识别出这个共性，一大类题都能套同一个模板。
如果要求返回最优的两个下标怎么办？+
在刷新 ans 时，把当时的 bestLeftIdx 和 j 一并记下来即可，本动画最后一帧的绿色高亮就是这么标出来的。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最佳观光组合 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。