Best Sightseeing Pair
Medium · Arrays & Hashing · Array · Dynamic Programming
Problem
You are given an integer array values, where values[i] is the rating of the i-th sightseeing spot. Visiting a pair of spots i < j scores
values[i] + values[j] + i - j
that is, the two ratings added together, minus the distance between the spots.
Return the highest score of any pair of spots.
Examples
Input: values = [3,7,2,6,5] Output: 11
Spots 1 and 3 score 7 + 6 + 1 - 3 = 11.
Input: values = [4,1] Output: 4
The only pair scores 4 + 1 + 0 - 1 = 4.
Input: values = [8,1,1,9,2] Output: 14
Spots 0 and 3 score 8 + 9 + 0 - 3 = 14; no closer pair does better.
Constraints
- 2 <= len(values) <= 5 · 10^4
- 1 <= values[i] <= 1000
Approaches
- Baseline: try every pair — time O(n²), space O(1)
Follow-up
The same split solves any score of the form f(i) + g(j) with i < j, such as the largest values[j] - values[i] (best time to buy and sell once). If the pair must also be at most d apart, the running maximum becomes a sliding-window maximum over the last d spots, kept in a monotonic deque: still O(n).
Related problems
Start free on Cariara · Coding problems · System design studio
