1014. Best Sightseeing Pair
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 * 104
1 <= values[i] <= 1000
Solutions
Solution 1: Enumeration
We can enumerate $j$ from left to right while maintaining the maximum value of $values[i] + i$ for elements to the left of $j$, denoted as $mx$. For each $j$, the maximum score is $mx + values[j] - j$. The answer is the maximum of these maximum scores for all positions.
The time complexity is $O(n)$, where $n$ is the length of the array $\textit{values}$. The space complexity is $O(1)$.
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 |
|