⚡Flashcard Drill➔
NeetCode #800LC-1014MediumGreedy
← Back to All Problems

#800 · #1014 · Best Sightseeing Pair(最佳观光组合)

📌 Problem Statement & Constraints

Given an array values, the score of a pair (i, j) with i < j is values[i] + values[j] + i - j. Return the maximum score. Constraints: 2 <= values.length <= 5 * 10^4, 1 <= values[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Rewrite the score as (values[i] + i) + (values[j] - j) for i < j.
  2. As you scan j left to right, keep the best values[i] + i seen so far.
  3. The best score ending at j is best + values[j] - j.
  4. Update the running best with values[j] + j after computing the score, so i < j is respected.

💻 Benchmark Python3 Implementation

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        best = values[0]               # max of values[i] + i seen so far
        res = 0
        for j in range(1, len(values)):
            res = max(res, best + values[j] - j)
            best = max(best, values[j] + j)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): two scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Updating best before computing the score: that would allow i == j, violating i < j.
  • Maximising values[i] - i: the correct quantity is values[i] + i.
  • Using the full formula in a nested loop: O(n^2) and unnecessary.
  • Initialising best to 0: values are positive here, but values[0] is the correct seed for a clean invariant.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems