LeetCode 1014: Best Sightseeing Pair

Problem Restatement

We are given an integer array values of length n.

The score of a pair (i, j) where i < j is:

values[i] + values[j] + i - j

We need to return the maximum score over all valid pairs.

The official constraints state that 2 <= values.length <= 5 * 10^4 and 1 <= values[i] <= 1000.

Input and Output

Function shape:

def maxScoreSightseeingPair(values: list[int]) -> int:
    ...

Examples

Example 1:

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

Best pair: (0, 2): 8 + 5 + 0 - 2 = 11.

Answer:

11

Example 2:

values = [1, 2]

Only pair: (0, 1): 1 + 2 + 0 - 1 = 2.

Answer:

2

Key Insight

Rewrite the score as:

(values[i] + i) + (values[j] - j)

For a fixed j, the right term (values[j] - j) is fixed.

We want to maximize the left term (values[i] + i) over all i < j.

So we can scan from left to right, maintaining the best (values[i] + i) seen so far.

Algorithm

1. Initialize best_left = values[0] + 0.
2. Initialize result = 0.
3. For each j from 1 to n - 1:
   • Update result = max(result, best_left + values[j] - j).
   • Update best_left = max(best_left, values[j] + j).
4. Return result.

The update order matters: we update result before updating best_left to ensure i < j.

Correctness

At each position j, best_left holds the maximum (values[i] + i) for all i < j.

The current score for the best i and the current j is best_left + values[j] - j.

We track the maximum such score across all j.

After computing the score, we update best_left to include position j as a potential left index for future pairs.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def maxScoreSightseeingPair(self, values: list[int]) -> int:
        best_left = values[0] + 0
        result = 0

        for j in range(1, len(values)):
            result = max(result, best_left + values[j] - j)
            best_left = max(best_left, values[j] + j)

        return result

Code Explanation

best_left tracks the maximum values[i] + i seen so far:

best_left = values[0] + 0

For each j, compute the best pair score using this left:

result = max(result, best_left + values[j] - j)

Then update best_left to include position j as a future left:

best_left = max(best_left, values[j] + j)

The update to result must come before the update to best_left to preserve the i < j constraint.

Testing

def run_tests():
    s = Solution()

    assert s.maxScoreSightseeingPair([8, 1, 5, 2, 6]) == 11
    assert s.maxScoreSightseeingPair([1, 2]) == 2
    assert s.maxScoreSightseeingPair([1, 3, 5]) == 7
    assert s.maxScoreSightseeingPair([10, 1, 1]) == 10

    print("all tests passed")

run_tests()