#1014

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Sightseeing Pair

Compute the maximum sightseeing score efficiently using state transition dynamic programming and single-pass array iteration techniques.

array dynamic programming

Problem Statement

You are given an integer array values where each element represents the attractiveness score of a sightseeing spot. The distance between spots i and j is calculated as j - i.

The score for a pair of sightseeing spots (i < j) is defined as values[i] + values[j] + i - j. Return the highest possible score obtainable from any such pair in the array.

Examples

Example 1

Input: values = [8,1,5,2,6]

Output: 11

i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2

Input: values = [1,2]

Output: 2

Example details omitted.

Constraints

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

Solution Approach

Transform the scoring formula for dynamic programming

Rewrite the score as (values[i] + i) + (values[j] - j) to separate state tracking from future computation. This highlights the state transition pattern and enables one-pass updates.

Iterate with a running maximum

Maintain the maximum of values[i] + i as you iterate through the array. At each j, calculate values[j] - j plus the current max to find potential scores, updating the global maximum dynamically.

Optimize space and handle constraints

Since only the current running max is needed, you can achieve O(1) space usage. Ensure edge cases with small arrays or identical values are correctly handled to avoid off-by-one errors.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The algorithm scans the array once, computing max scores with a running maximum, giving O(n) time complexity. Only a single variable is stored for the running maximum, resulting in O(1) space usage.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumeration

We can enumerate $j$ from left to right while maintaining the maximum value of $values[i] + i$ for elements to the left of $j$, denoted as $mx$. For each $j$, the maximum score is $mx + values[j] - j$. The answer is the maximum of these maximum scores for all positions.

1

2

3

4

5

6

7

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

Continue Practicing

#1024 video stitching #1027 longest arithmetic subsequence #1000 minimum cost to merge stones