Problem

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 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 the distance between them.

Return the maximum score of a pair of sightseeing spots.

Examples

Example 1:

1
2
3

Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2:

1
2

Input: values = [1,2]
Output: 2

Constraints:

  • 2 <= values.length <= 5 * 104
  • 1 <= values[i] <= 1000

Similar Problem

Special Array 1

Solution

Method 1 - Using Kadane’s Algorithm

The problem requires us to find the maximum score of a pair of sightseeing spots, where the score is given by values[i] + values[j] + i - j with the condition i < j.

To simplify the problem, notice that the expression can be rearranged:

$$ \text{score} = values[i] + i + values[j] - j $$ From this rearrangement, “values[i] + i” can be seen as one component and “values[j] - j” as another. Our goal becomes finding the maximum of “values[i] + i” up to i < j and then the maximum values[j] - j for j > i.

We can use a single scan with dynamic programming:

  1. Initialize maxI to values[0] + 0.
  2. Iterate over the array and compute maxI and the current score.
  3. Update the maximum score if the current score is greater than the previously recorded maximum score.
  4. Update maxI to be the maximum value of its previous value and values[i] + i.

Code

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

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxI = values[0] + 0;
        int ans = Integer.MIN_VALUE;
        
        for (int j = 1; j < values.length; j++) {
            ans = Math.max(ans, maxI + values[j] - j);
            maxI = Math.max(maxI, values[j] + j);
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        maxI: int = values[0] + 0
        ans: int = float('-inf')
        
        for j in range(1, len(values)):
            ans = max(ans, maxI + values[j] - j)
            maxI = max(maxI, values[j] + j)
            
        return ans

Complexity

  • ⏰ Time complexity: O(n) because we traverse the array only once.
  • 🧺 Space complexity: O(1) since we use a constant amount of extra space.