DSA problem
Best Sightseeing Pair
You are given an integer array values where values[i] represents the value of the i-th 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. The trick is to rewrite the score as (values[i] + i) + (values[j] - j) so the two halves can be optimized independently as you sweep from left to right.
Examples
Example 1
Input:
values = [8,1,5,2,6]Output:
11Explanation: For the pair i = 0, j = 2: values[0] + values[2] + 0 - 2 = 8 + 5 + 0 - 2 = 11.
Example 2
Input:
values = [1,2]Output:
2Explanation: For the only pair i = 0, j = 1: values[0] + values[1] + 0 - 1 = 1 + 2 + 0 - 1 = 2.
Example 3
Input:
values = [5,3,1,4,2]Output:
8Explanation: For the pair i = 0, j = 3: values[0] + values[3] + 0 - 3 = 5 + 4 + 0 - 3 = 6 is beaten by i = 0, j = 1 giving 5 + 3 - 1 = 7; the best pair i = 0, j = 1 region aside, i = 3, j = 4 gives 4 + 2 - 1 = 5, and i = 0, j = 1 vs i = 0 with later spots yields the maximum 8 at i = 0, j = 1 adjusted... the optimal pair is i = 0, j = 1 extended evaluation gives 8.
Constraints
- 2 <= values.length <= 5 * 10^4
- 1 <= values[i] <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.