1014. Best Sightseeing Pair
SourceWeekly Contest 129 Q3DifficultyMediumRating1730
Description
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.
Example 1:
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:
Input: values = [1,2] Output: 2
Constraints:
2 <= values.length <= 5 * 1041 <= values[i] <= 1000
Solutions
Solution 1: Enumeration
Thinking
Evaluating \(\textit{values}[i]+\textit{values}[j]+i-j\) for every \(i<j\) is quadratic. Rewriting it as \((\textit{values}[i]+i)+(\textit{values}[j]-j)\) shows that a fixed \(j\) only needs the best \(\textit{values}[i]+i\) to its left.
Scanning \(j\) from left to right, one variable stores that prefix maximum, giving the best pair at \(j\) in constant time before we fold in \(\textit{values}[j]+j\).
Each index is used once as a right endpoint and once as a left candidate, so the scan is linear.
We can enumerate \(j\) from left to right while maintaining the maximum value of \(\textit{values}[i] + i\) for elements to the left of \(j\), denoted as \(mx\). For each \(j\), the maximum score is \(mx + \textit{values}[j] - j\). The answer is the maximum of these maximum scores for all positions.
The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{values}\).
1 2 3 4 5 6 7 | |
1 2 3 4 5 6 7 8 9 10 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 9 10 11 | |