Best Sightseeing Pair - Leetcode Solution

The Best Sightseeing Pair problem on LeetCode is as follows:

You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance of j - i between them.

The score of a pair (i < j) of sightseeing spots is (values[i] + values[j] + i - j): the sum of the values of the sightseeing spots, minus their distance.

Return the maximum score of a pair of sightseeing spots.

Example:

Input: values = [8,1,5,2,6] Output: 11 Explanation: The maximum score is achieved by pairs (values[2], values[4]) = (5, 6). The score is (5 + 6 + 2 - 4) = 9 + 2 = 11.

Solution:

One way to solve this problem is to use dynamic programming to keep track of the maximum score pairs that end at each sightseeing spot. We can start by initializing two variables - max_so_far and res - to 0. We can then iterate over the array and for each sightseeing spot i, we can update max_so_far to be the maximum of max_so_far and values[i]+i, and update res to be the maximum of res and max_so_far + values[j] - j, where j is the current index and we are looking for a pair with a larger score than the current maximum.

Here's the Python code for this solution:

class Solution: def maxScoreSightseeingPair(self, values: List[int]) -> int: max_so_far = 0 res = 0 for j in range(len(values)): res = max(res, max_so_far + values[j] - j) max_so_far = max(max_so_far, values[j] + j) return res

Time Complexity: O(n), where n is the length of the input array. Space Complexity: O(1), constant space is used.

1