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
- Rewrite the score as
(values[i] + i) + (values[j] - j)fori < j. - As you scan
jleft to right, keep the bestvalues[i] + iseen so far. - The best score ending at
jisbest + values[j] - j. - Update the running best with
values[j] + jafter computing the score, soi < jis 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
bestbefore computing the score: that would allowi == j, violatingi < j. - Maximising
values[i] - i: the correct quantity isvalues[i] + i. - Using the full formula in a nested loop: O(n^2) and unnecessary.
- Initialising
bestto 0: values are positive here, butvalues[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.