Understanding the Problem

The score formula values[i] + values[j] + i - j rewards spots with high values but penalizes distance between them. Two amazing spots on opposite ends of the array might score lower than two decent spots right next to each other.

We need to find the pair (i, j) with i < j that maximizes this score. The brute force approach is to try all pairs, but is there a way to avoid that?

Here's the key: rearrange the formula. Group the terms by index:

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

This splits the score into two independent parts: one that depends only on i, and one that depends only on j. For any fixed j, maximizing the score means maximizing values[i] + i over all valid i < j. That's just a running maximum.

Key Constraints:

2 <= values.length <= 5 * 10^4 means an O(n^2) brute force is borderline (up to 2.5 billion operations). We should aim for O(n).
All values are positive (1 <= values[i] <= 1000), so the score is always at least values[0] + values[1] - 1 >= 1. No need to worry about negative scores.

Approach 1: Brute Force

Intuition

The most direct approach: try every pair (i, j) where i < j, compute the score, and keep the maximum. This is guaranteed to find the answer because we're exhaustively checking every valid pair.

Algorithm

Initialize maxScore to 0
For each index i from 0 to n-2:

For each index j from i+1 to n-1:

Compute score = values[i] + values[j] + i - j
Update maxScore if this score is larger

Return maxScore

Example Walkthrough

1Initialize: maxScore=0, check all pairs (i, j) where i < j

1/7

Code

Complexity Analysis

Time Complexity: O(n^2). Two nested loops, each iterating up to n times. We check roughly n*(n-1)/2 pairs, doing O(1) work per pair.
Space Complexity: O(1). Only a single variable maxScore regardless of input size.

For each index j, we scan backwards through every previous index i to find the best pair. That means we're recomputing the "best left partner" for every single j, even though the best left partner can only change by considering one new element at a time. What if we tracked the best left partner as we go, so we never had to look back?

Approach 2: Decomposition with Running Maximum

Intuition

Here's the algebraic insight that cracks this problem open. The score formula is:

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

Rearrange by grouping terms that belong to the same index:

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

Now the score is the sum of two independent parts. The first part, values[i] + i, depends only on the left spot. The second part, values[j] - j, depends only on the right spot. For any fixed j, maximizing the total score means maximizing values[i] + i among all i < j.

This is the exact same pattern as "Best Time to Buy and Sell Stock": as we scan left to right, we maintain a running maximum of values[i] + i (the "best left partner seen so far"). At each position j, we combine that running max with values[j] - j to get the best possible score ending at j.

Why does this work?

The decomposition (values[i] + i) + (values[j] - j) works because the distance penalty i - j distributes cleanly between the two indices. The +i goes with the left spot and the -j goes with the right spot. Once separated, the problem becomes: for each right spot j, find the left spot i < j that maximizes values[i] + i. Since we only need the maximum of everything we've seen so far (not anything about which specific index it came from), a running maximum is all we need.

This is a greedy approach: we never need to reconsider a past decision. If a new index has a higher values[i] + i, it's strictly better as a left partner for all future right spots, so we update our running max.

Algorithm

Initialize maxLeftScore to values[0] + 0 (the values[i] + i contribution of the first spot)
Initialize maxScore to 0
For each index j from 1 to n-1:

Compute the score using the best left partner: maxLeftScore + values[j] - j
Update maxScore if this is better
Update maxLeftScore if values[j] + j is larger (this position becomes the new best left partner for future j's)

Return maxScore

Example Walkthrough

1Initialize: maxLeftScore = values[0]+0 = 8, maxScore = 0

maxLeft=8

1/6

Code

Complexity Analysis

Time Complexity: O(n). A single pass through the array, doing O(1) work per element.
Space Complexity: O(1). Two variables (maxLeftScore and maxScore) regardless of input size.

Best Sightseeing Pair

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Decomposition with Running Maximum

Intuition

Algorithm

Example Walkthrough

Code

Get Premium