Best Sightseeing Pair

You can approach this problem by finding the maximum score of a pair of sightseeing spots. You need to maximize ( \text{values}[i] + \text{values}[j] + i - j ) for all ( i < j ).

Here’s the code to do that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        max_score = 0
        current_score = values[0]

        for j in range(1, len(values)):
            # The score for the current pair (i, j)
            max_score = max(max_score, current_score + values[j] - j)

            # Update the current_score for the next iteration
            current_score = max(current_score, values[j] + j)

        return max_score

The idea is to iterate through the sightseeing spots and maintain a running maximum of the score as current_score. By tracking the running maximum, you can update the maximum score for each pair efficiently, resulting in an (O(n)) time complexity.