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.
For example:
values = [8, 1, 5, 2, 6]
should return 11, because i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
values = [1, 2]
should return 2.Could you provide an efficient algorithm to solve this problem?
The naive solution involves checking all possible pairs of sightseeing spots (i, j) where i < j and calculating the score for each pair. Then, we return the maximum score found.
def max_sightseeing_pair_brute_force(values):
max_score = 0
n = len(values)
for i in range(n):
for j in range(i + 1, n):
score = values[i] + values[j] + i - j
max_score = max(max_score, score)
return max_score
O(n^2), where n is the number of sightseeing spots, because we have nested loops.
O(1), as we only use a constant amount of extra space.
We can optimize the solution by realizing that the score can be expressed as values[i] + values[j] + i - j
. We can rearrange this to (values[i] + i) + (values[j] - j)
. Therefore, we want to maximize values[i] + i
for each i
and values[j] - j
for each j > i
.
We can iterate through the values
array, keeping track of the maximum value of values[i] + i
encountered so far. For each j
, we can calculate the score using the maximum values[i] + i
and values[j] - j
, and update the maximum score accordingly.
def max_sightseeing_pair_optimal(values):
max_score = 0
max_i_plus_i = values[0] + 0
n = len(values)
for j in range(1, n):
score = max_i_plus_i + values[j] - j
max_score = max(max_score, score)
max_i_plus_i = max(max_i_plus_i, values[j] + j)
return max_score
O(n), where n is the number of sightseeing spots, as we iterate through the array once.
O(1), as we only use a constant amount of extra space.
values
is between 2 and 5 * 10^4, so we don't need to handle an empty input.values[i]
are between 1 and 1000, so we don't need to worry about integer overflow.