最佳观光组合 图解题解

这道题到底在挑哪两个景点

给一排景点评分 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），否则起点太大正确答案就刷不进去。

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 ans

C++

#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;
    }
}