Problem Description

You have an array values where each element values[i] represents the value of a sightseeing spot at position i.

When visiting two sightseeing spots at positions i and j (where i < j), you need to consider both their values and the distance between them. The distance between spots i and j is simply j - i.

The score for visiting a pair of spots (i, j) is calculated as: values[i] + values[j] + i - j. This formula adds the values of both spots, then adjusts for their positions by adding i and subtracting j.

Your task is to find the maximum possible score among all valid pairs of sightseeing spots.

For example, if you have spots at positions i = 1 and j = 4 with values values[1] = 8 and values[4] = 5, the score would be 8 + 5 + 1 - 4 = 10.

The key insight is that the score formula values[i] + values[j] + i - j can be rearranged as (values[i] + i) + (values[j] - j). This allows us to track the maximum value of values[i] + i seen so far as we iterate through the array, then for each position j, calculate the score using the best previous position.

Intuition

Looking at the score formula values[i] + values[j] + i - j, we need to find the maximum value across all valid pairs where i < j. A brute force approach would check all possible pairs, but this would be inefficient.

The key observation is that we can rearrange the formula by grouping terms related to each index: values[i] + values[j] + i - j = (values[i] + i) + (values[j] - j)

This rearrangement reveals that for any fixed position j, the score depends on two independent parts:

• A term from position i: values[i] + i
• A term from position j: values[j] - j

Since we want to maximize the total score for each j, we should pair it with the position i (where i < j) that has the maximum value of values[i] + i.

This leads to an efficient approach: as we iterate through the array from left to right, we can:

1. Keep track of the maximum value of values[i] + i seen so far (this represents the best left position)
2. For each position j, calculate the score using this maximum value plus values[j] - j
3. Update our running maximum of values[i] + i to include the current position for future iterations

This way, we only need a single pass through the array, checking each position once as a potential right endpoint j, while maintaining the best possible left endpoint i we've seen so far.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using a single pass enumeration approach with two tracking variables:

1. Initialize tracking variables:

   • ans: Stores the maximum score found so far, initialized to 0
   • mx: Tracks the maximum value of values[i] + i seen so far, initialized to 0

2. Enumerate through the array: We iterate through each position j from left to right using enumerate(values) to get both the index and value.

3. For each position j:

   • Calculate the score: Using the current position as the right endpoint, we compute the score as mx + x - j, where:

     • mx represents the best values[i] + i from all previous positions
     • x is values[j] (the current value)
     • The formula mx + x - j equals (values[i] + i) + (values[j] - j) for the best previous i

   • Update the maximum score: Compare the calculated score with ans and keep the larger value: ans = max(ans, mx + x - j)

   • Update mx for future iterations: After using position j as a right endpoint, we consider it as a potential left endpoint for future positions. Update mx to be the maximum of its current value and x + j (which is values[j] + j): mx = max(mx, x + j)

4. Return the result: After processing all positions, ans contains the maximum score among all valid pairs.

The algorithm maintains the invariant that at each step j, mx contains the maximum value of values[i] + i for all i < j, ensuring we always pair each right endpoint with the optimal left endpoint. This achieves O(n) time complexity with O(1) space complexity.

Example Walkthrough

Let's walk through the solution with values = [8, 1, 5, 2, 6].

We want to find the maximum score where score = values[i] + values[j] + i - j for i < j.

Initial State:

• ans = 0 (maximum score found)
• mx = 0 (maximum of values[i] + i seen so far)

Iteration 1 (j=0, value=8):

• Calculate score using j=0 as right endpoint: mx + 8 - 0 = 0 + 8 - 0 = 8
• Update ans = max(0, 8) = 8
• Update mx = max(0, 8 + 0) = 8 (now j=0 can be a left endpoint for future positions)

Iteration 2 (j=1, value=1):

• Calculate score with best left endpoint (i=0): mx + 1 - 1 = 8 + 1 - 1 = 8
  • This represents the pair (0,1) with score: values[0] + values[1] + 0 - 1 = 8 + 1 + 0 - 1 = 8
• Update ans = max(8, 8) = 8
• Update mx = max(8, 1 + 1) = 8

Iteration 3 (j=2, value=5):

• Calculate score with best left endpoint: mx + 5 - 2 = 8 + 5 - 2 = 11
  • This represents the pair (0,2) with score: values[0] + values[2] + 0 - 2 = 8 + 5 + 0 - 2 = 11
• Update ans = max(8, 11) = 11
• Update mx = max(8, 5 + 2) = 8

Iteration 4 (j=3, value=2):

• Calculate score with best left endpoint: mx + 2 - 3 = 8 + 2 - 3 = 7
• Update ans = max(11, 7) = 11
• Update mx = max(8, 2 + 3) = 8

Iteration 5 (j=4, value=6):

• Calculate score with best left endpoint: mx + 6 - 4 = 8 + 6 - 4 = 10
• Update ans = max(11, 10) = 11
• Update mx = max(8, 6 + 4) = 10

Result: The maximum score is 11, achieved by the pair (0,2).

We can verify: values[0] + values[2] + 0 - 2 = 8 + 5 - 2 = 11 ✓

The key insight is that mx always maintains the best possible left endpoint value (values[i] + i) for any future right endpoint, allowing us to find the optimal pair in a single pass.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array values. This is because the algorithm iterates through the array exactly once using a single for loop, performing constant-time operations (max comparisons and arithmetic operations) at each iteration.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size, storing just three variables: ans, mx, and the loop variables j and x. No additional data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order of Operations

Pitfall: A common mistake is updating max_left_value before calculating the current score. This would incorrectly allow pairing position j with itself.

Incorrect Implementation:

for j, value_j in enumerate(values):
    # WRONG: Updating max_left_value first
    max_left_value = max(max_left_value, value_j + j)
    current_score = max_left_value + value_j - j  # This could use j paired with itself!
    max_score = max(max_score, current_score)

Why it's wrong: If we update max_left_value first, when calculating the score for position j, we might be using values[j] + j as the left value, effectively pairing j with itself, which violates the constraint i < j.

Solution: Always calculate the score first, then update max_left_value:

for j, value_j in enumerate(values):
    # Calculate score BEFORE updating max_left_value
    current_score = max_left_value + value_j - j
    max_score = max(max_score, current_score)
    # Update max_left_value AFTER using j as right endpoint
    max_left_value = max(max_left_value, value_j + j)

2. Misunderstanding the Score Formula

Pitfall: Incorrectly implementing the score calculation by not properly decomposing the formula.

Incorrect Implementation:

# WRONG: Trying to track values[i] - i instead of values[i] + i
max_left_value = values[0] - 0
for j in range(1, len(values)):
    current_score = max_left_value + values[j] + j  # Wrong formula!
    max_score = max(max_score, current_score)
    max_left_value = max(max_left_value, values[j] - j)

Solution: Remember that the score formula values[i] + values[j] + i - j decomposes into (values[i] + i) + (values[j] - j). Track values[i] + i as the left component, not values[i] - i.

3. Edge Case Handling

Pitfall: Not handling arrays with only 2 elements or initializing variables incorrectly.

Incorrect Implementation:

# WRONG: Starting from index 1 without proper initialization
max_left_value = values[0] + 0
max_score = 0
for j in range(1, len(values)):  # What if we miss valid pairs?
    current_score = max_left_value + values[j] - j
    max_score = max(max_score, current_score)
    max_left_value = max(max_left_value, values[j] + j)

Solution: Initialize both max_score and max_left_value to 0, then process all elements including index 0. This ensures the algorithm works correctly even when the first element isn't part of the optimal pair:

max_score = 0
max_left_value = 0
for j, value_j in enumerate(values):
    current_score = max_left_value + value_j - j
    max_score = max(max_score, current_score)
    max_left_value = max(max_left_value, value_j + j)