LeetCode 1014题解：动态规划优化最佳观光组合问题-嵌云网-嵌入式AI开发资源站

LeetCode 1014题解：动态规划优化最佳观光组合问题

董云舟·2026-10-30·阅读 25 GEO检测（免费）

动态规划LeetCode数组优化

|难度：普通|阅读约 8 分钟

1. 问题背景与题目解析

最佳观光组合（Best Sightseeing Pair）是LeetCode上的一道中等难度动态规划题目，编号1014。这道题的核心在于理解题目描述中那个看似简单却暗藏玄机的评分公式。

题目给出一个正整数数组values，其中values[i]表示第i个观光景点的评分。我们需要找到一对景点(i,j)（其中i<j），使得评分score=values[i]+values[j]+i-j达到最大值。换句话说，我们要在数组中找到两个元素，使它们的和加上索引差（i-j）达到最大。

这个评分公式可以拆解为：

code复制score = (values[i] + i) + (values[j] - j)

这个变形非常关键，它揭示了问题的本质——我们需要分别最大化(values[i]+i)和(values[j]-j)这两个部分。由于i必须小于j，所以可以在遍历数组时，维护一个变量来记录当前元素之前最大的(values[i]+i)，然后与当前的(values[j]-j)相加，得到当前的最大评分。

需要模型API调用？免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。

2. 暴力解法与时间复杂度分析

对于刚接触这道题的新手，最直观的想法可能是使用双重循环的暴力解法：

python复制def maxScoreSightseeingPair(values):
    max_score = 0
    n = len(values)
    for i in range(n):
        for j in range(i+1, n):
            current = values[i] + values[j] + i - j
            max_score = max(max_score, current)
    return max_score

这种解法的时间复杂度是O(n²)，当n较大时（比如n=50000），计算量会达到25亿次操作，这在LeetCode上会导致超时（TLE）。因此，我们需要寻找更高效的解法。

提示：在LeetCode中，n的规模通常在10^4到10^5之间，O(n²)的算法几乎肯定会导致超时，因此必须寻找线性或对数级别的解法。

3. 动态规划解法详解

基于第一节的公式变形，我们可以设计一个O(n)时间复杂度的动态规划解法。核心思路是在遍历数组时，维护两个关键变量：

max_prev：记录遍历到当前位置之前，最大的(values[i]+i)值
max_score：记录全局最大评分

具体实现如下：

python复制def maxScoreSightseeingPair(values):
    max_prev = values[0] + 0  # 初始化为第一个元素的values[i]+i
    max_score = 0
    
    for j in range(1, len(values)):
        # 计算当前评分
        current_score = max_prev + values[j] - j
        max_score = max(max_score, current_score)
        
        # 更新max_prev为当前j位置之前最大的values[i]+i
        max_prev = max(max_prev, values[j] + j)
    
    return max_score

这个解法只需要一次遍历，时间复杂度降为O(n)，空间复杂度为O(1)，完美解决了大规模数据的问题。

4. 算法正确性证明与边界条件

为了验证这个算法的正确性，让我们考虑几个关键点：

变量维护的正确性：max_prev始终保存了当前位置之前最大的(values[i]+i)，这保证了我们在计算每个j位置的评分时，都能使用到最优的i值。
遍历顺序的正确性：由于i必须小于j，我们从左到右遍历，先更新max_score再更新max_prev，确保了i和j的相对位置关系。
边界条件处理：
- 数组长度为2时，直接返回values[0]+values[1]-1
- 所有元素相同时，最大评分为values[0]+values[1]-1
- 数组元素递减时，最大评分通常出现在前两个元素

测试用例示例：

python复制assert maxScoreSightseeingPair([8,1,5,2,6]) == 11  # 8 + 6 + 0 - 3 = 11
assert maxScoreSightseeingPair([1,2]) == 2         # 1 + 2 + 0 - 1 = 2
assert maxScoreSightseeingPair([5,5,5,5]) == 9     # 5 + 5 + 0 - 1 = 9

5. 算法优化与变种思考

这道题的核心优化点在于将原始公式拆分为(values[i]+i)和(values[j]-j)两部分，这种拆分技巧在很多数组问题中都有应用。类似的技巧还包括：

前缀和：将累加问题转化为前缀和之差
滑动窗口：维护一个窗口内的统计信息
双指针：从两端向中间遍历

对于这道题的变种，可以考虑：

如果要求三个景点的最佳组合，公式变为values[i]+values[j]+values[k]+i-j-k，可以扩展我们的解法，维护两个变量max_prev1和max_prev2
如果距离计算改为绝对距离|i-j|，问题会变得更加复杂，可能需要分情况讨论

6. 实际应用场景与类似问题

这道题虽然以观光景点为背景，但其核心算法可以应用于许多实际问题：

股票买卖时机选择：寻找i<j使prices[j]-prices[i]最大
广告投放优化：在不同时段投放广告，考虑时间衰减因素
资源调度：在不同时间点分配资源，考虑时间成本

LeetCode上类似的题目包括：

1. Best Time to Buy and Sell Stock
1. Maximum Subarray
1. Maximum Product Subarray

7. 刷题心得与效率提升

在解决这类数组优化问题时，我有以下几点经验分享：

公式变形是关键：很多数组问题都可以通过巧妙的数学变形转化为更易处理的形式。在这道题中，将原始公式拆分为(values[i]+i)+(values[j]-j)是突破口。
维护辅助变量：在单次遍历中维护关键变量（如max_prev）是降低时间复杂度的常用技巧。
边界测试不可少：一定要测试数组长度为0、1、2的情况，以及所有元素相同、递增、递减等特殊情况。
从暴力解法入手：即使知道暴力解法不行，先写出暴力解法有助于理解问题本质，然后再思考优化方向。
画图辅助理解：对于数组问题，在纸上画出几个元素的示例，标出i和j的位置关系，往往能发现规律。

在实际刷题过程中，建议将这类问题归类为"数组优化"或"动态规划"类别，总结它们的共性和解题模板。这道Best Sightseeing Pair就是一个典型的通过维护前缀最大值来优化计算的例子，掌握这个模式后，可以解决一系列类似问题。