What is the optimal time complexity for Best Sightseeing Pair?

Using a single-pass dynamic programming approach, you can achieve O(n) time and O(1) space by tracking the running maximum of values[i] + i.

How do I transform the score formula for easier computation?

Rewrite values[i] + values[j] + i - j as (values[i] + i) + (values[j] - j) to separate state tracking and enable efficient iteration.

Can arrays of length 2 be handled without special cases?

Yes, even the smallest arrays can be processed in one pass using the same running maximum approach; ensure indices are correctly compared.

Why is this problem classified under state transition dynamic programming?

Because the solution maintains a running state (max of values[i]+i) that is updated as you progress, directly reflecting state transition patterns.

What common mistakes should I avoid when implementing this solution?

Avoid nested loops, misplacing the running maximum update, and incorrectly handling edge cases like identical values or minimal-length arrays.

#1014

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最佳观光组合

给你一个正整数数组 values ，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i 。一对景点（ i ）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和减去它们两者之间的距…

数组动态规划

题目描述

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和减去它们两者之间的距离。

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

示例 1：

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

示例 2：

输入：values = [1,2]
输出：2

提示：

2 <= values.length <= 5 * 10⁴
1 <= values[i] <= 1000

lightbulb

解题思路

方法一：枚举

我们可以从左到右枚举 $j$ ，同时维护 $j$ 左侧元素中 $values[i] + i$ 的最大值 $mx$ ，这样对于每个 $j$ ，最大得分为 $mx + values[j] - j$ 。我们取所有位置的最大得分的最大值即为答案。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{values}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        ans = mx = 0
        for j, x in enumerate(values):
            ans = max(ans, mx + x - j)
            mx = max(mx, x + j)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Are you able to simplify the score formula to support a dynamic programming approach?
question_mark
Can you track the best candidate so far in a single pass without extra arrays?
question_mark
How do you ensure your solution handles the largest input sizes efficiently?

warning

常见陷阱

外企场景

error
Forgetting to separate i and j components in the score, leading to nested loops and O(n^2) time.
error
Updating the running maximum after computing the score for j instead of before.
error
Incorrectly handling arrays of length 2 or when all values are identical.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return not just the max score but also the indices of the best sightseeing pair.
arrow_right_alt
Extend the problem to allow skipping certain spots or weighting distances differently.
arrow_right_alt
Compute the k highest scores from multiple non-overlapping sightseeing pairs.

help

常见问题

外企场景

继续练习

#1024 视频拼接 #1027 最长等差数列 #1000 合并石头的最低成本