题目描述
思路解析
一句话答案：LeetCode 1014 最佳观光组合：得分拆成 (values[i]+i) 加 (values[j]−j)，遍历 j 维护左边 values[i]+i 的最大值 best，一遍扫描取最优，时间 O(n)、空间 O(1)。
这道题到底在挑哪两个景点
给一排景点评分 values，任取两个不同景点，下标小的记 i、大的记 j（i 小于 j），得分是 values[i]+values[j]+i−j，要在所有点对里找最高分。
两个评分越高越好，但下标差 j−i 越大扣得越多——离得远的一对哪怕评分高，也可能被距离拖垮，不能只挑评分最高的两个。
为什么两两都配一遍会超时
双重循环把约 n²/2 对点对全算一遍，几万规模就是几十亿次配对，O(n²)（大 O 记号，规模变大时运算量怎么涨）跑不完。
慢在每换一个右端 j，都把它左边所有候选从头再扫一遍。只要扫到 j 就立刻知道左边最好的搭档是谁，一层循环就够。
为什么把 i−j 拆到两个下标身上
得分 values[i]+values[j]+i−j 难在 i 和 j 缠在一个式子里。把 +i 归给左端、把 −j 归给右端，重写成 (values[i]+i)+(values[j]−j)，两个下标就各管各了。
固定右端 j 后 (values[j]−j) 是定值，只需让左边的 (values[i]+i) 最大。于是维护一个变量 best，记扫到当前 j 时它左边所有 values[i]+i 里的最大值——这个前缀最大值，就是本题动态规划塌成的一个滚动变量。
扫到每个 j 是先算分还是先更新
遍历右端 j 做两件事，顺序要紧：先用 best+values[j]−j 结算这对得分刷新答案，此刻 best 还只含 j 左边的候选；再把 values[j]+j 纳入 best，让 j 成为后面的候选左端。
顺序必须先结算、后更新。若先把 values[j]+j 塞进 best，best 就可能是 j 自己，等于让景点自我配对，i 小于 j 破掉。参考代码里 best_left 初始化成 values[0]，ans 从极小值起，循环从下标 1 起。
拿 [8,1,5,2,6] 一遍扫到底
best 初值 values[0]+0=8。下标 1：得分 8+1−1=8，答案刷成 8；values[1]+1=2 没超 8，best 不动。下标 2：得分 8+5−2=11，答案刷成 11；values[2]+2=7 没超 8。
下标 3：8+2−3=7，没超 11。下标 4：8+6−4=10，没超 11；values[4]+4=10 超过 8，best 更新成 10，但已到末尾。扫完答案 11，即选下标 0 和下标 2：8+5+0−2=11，与题面吻合。
先更新 best 再结算，答案为什么会虚高
把两步顺序倒过来：先拿 values[j]+j 更新 best、再结算。best 里就可能混进 j 自己，等于把同一个景点配成一对，距离 j−i 变成 0、白拿两份评分，i 小于 j 失守。
复杂度上只从头扫一遍、每步常数次运算，时间 O(n)；只留 best、ans 两个变量，空间 O(1)。两处别马虎：只有两个元素时 best 就是下标 0，循环只结算一次；ans 初值要够小（参考代码用 −10^18），否则起点太大正确答案就刷不进去。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「拆成 (values[i]+i)+(values[j]−j)，扫 j 维护左边最大的 values[i]+i」，下面每帧都在套它。
开局把第 0 个景点作为左端候选：bestLeft = values[0]+0 = 8（绿色标出当前最佳左端）。从 j=1 开始，每个 j 都拿 bestLeft 来配对。
右端点走到第 1 个（评分 1）。配上左边最佳端点（绿色，下标 0）：得分 8 + 1 − 1 = 8。比旧的最大得分更高，刷新 ans=8。
第 1 个作为左端候选只有 values[1]+1 = 2，没超过 bestLeft=8，最佳左端不动，绿色仍停在下标 0。
右端点走到第 2 个（评分 5）。配上左边最佳端点（绿色，下标 0）：得分 8 + 5 − 2 = 11。比旧的最大得分更高，刷新 ans=11。
第 2 个作为左端候选只有 values[2]+2 = 7，没超过 bestLeft=8，最佳左端不动，绿色仍停在下标 0。
右端点走到第 3 个（评分 2）。配上左边最佳端点（绿色，下标 0）：得分 8 + 2 − 3 = 7。没超过当前最大 ans=11，保持。
第 3 个作为左端候选只有 values[3]+3 = 5，没超过 bestLeft=8，最佳左端不动，绿色仍停在下标 0。
右端点走到第 4 个（评分 6）。配上左边最佳端点（绿色，下标 0）：得分 8 + 6 − 4 = 10。没超过当前最大 ans=11，保持。
再把第 4 个也纳入「左端候选」：values[4]+4 = 10，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 4，bestLeft=10。后面的 j 会用这个更优的左端。
右端点走到第 5 个（评分 7）。配上左边最佳端点（绿色，下标 4）：得分 10 + 7 − 5 = 12。比旧的最大得分更高，刷新 ans=12。
再把第 5 个也纳入「左端候选」：values[5]+5 = 12，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 5，bestLeft=12。后面的 j 会用这个更优的左端。
右端点走到第 6 个（评分 3）。配上左边最佳端点（绿色，下标 5）：得分 12 + 3 − 6 = 9。没超过当前最大 ans=12，保持。
第 6 个作为左端候选只有 values[6]+6 = 9，没超过 bestLeft=12，最佳左端不动，绿色仍停在下标 5。
右端点走到第 7 个（评分 9）。配上左边最佳端点（绿色，下标 5）：得分 12 + 9 − 7 = 14。比旧的最大得分更高，刷新 ans=14。
再把第 7 个也纳入「左端候选」：values[7]+7 = 16，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 7，bestLeft=16。后面的 j 会用这个更优的左端。
右端点走到第 8 个（评分 4）。配上左边最佳端点（绿色，下标 7）：得分 16 + 4 − 8 = 12。没超过当前最大 ans=14，保持。
第 8 个作为左端候选只有 values[8]+8 = 12，没超过 bestLeft=16，最佳左端不动，绿色仍停在下标 7。
右端点走到第 9 个（评分 10）。配上左边最佳端点（绿色，下标 7）：得分 16 + 10 − 9 = 17。比旧的最大得分更高，刷新 ans=17。
再把第 9 个也纳入「左端候选」：values[9]+9 = 19，比旧的 bestLeft 大，于是最佳左端（绿色）移到下标 9，bestLeft=19。后面的 j 会用这个更优的左端。
扫完全程，最优是绿色这一对：下标 7（评分 9）和下标 9（评分 10），得分 9+10+7−9 = 17。一遍扫描、不回头就锁定了答案。
边界先想清：两元素只有一对；递减时越靠前越好。
两个追问，核心是认出「前缀最优 + 一遍扫描」这个母题。
参考代码
from typing import Listclass 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 ans复杂度
- 时间：O(n)，只扫一遍
- 空间：O(1)，只用 bestLeft、ans 两个变量
易错点
面试追问把动画讲成自己的话
追问这题和「买卖股票 LC121」像在哪？
追问如果要求返回最优的两个下标怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
视频拼接
LeetCode 1024 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题