1014. Best Sightseeing Pair

[mah-shamim]

Topics: Array, Dynamic Programming

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

Hint:

1. Can you tell the best sightseeing spot in one pass (ie. as you iterate over the input?) What should we store or keep track of as we iterate to do this?

[mah-shamim]

We can use a single-pass approach with a linear time complexity O(n). The idea is to keep track of the best possible values[i] + i as we iterate through the array. This allows us to maximize the score values[i] + values[j] + i - j for every valid pair (i, j).

Let's implement this solution in PHP: 1014. Best Sightseeing Pair

<?php
/**
 * @param Integer[] $values
 * @return Integer
 */
function maxScoreSightseeingPair($values) {
    $maxScore = 0;
    $maxI = $values[0]; // Track the maximum values[i] + i

    for ($j = 1; $j < count($values); $j++) {
        // Calculate the score for the current pair
        $maxScore = max($maxScore, $maxI + $values[$j] - $j);

        // Update maxI to track the best values[i] + i for the next iteration
        $maxI = max($maxI, $values[$j] + $j);
    }

    return $maxScore;
}

// Example usage:
$values1 = [8, 1, 5, 2, 6];
echo maxScoreSightseeingPair($values1); // Output: 11

$values2 = [1, 2];
echo maxScoreSightseeingPair($values2); // Output: 2
?>

Explanation:

1. Initialization:

   • maxI is initialized to values[0] because we start evaluating pairs from index 1.
   • maxScore is initialized to 0 to track the maximum score.

2. Iterate Over the Array:

   • For each index j starting from 1, calculate the score for the pair (i, j) using the formula:
     Score = maxI + values[j] - j
   • Update maxScore with the maximum value obtained.

3. Update maxI:

   • Update maxI to track the maximum possible value of values[i] + i for the next iterations.

4. Return the Maximum Score:

   • After iterating through the array, maxScore will contain the maximum score for any pair.

Complexity:

• Time Complexity: O(n) because we loop through the array once.
• Space Complexity: O(1) as we use a constant amount of space.

This solution efficiently computes the maximum score while adhering to the constraints and is optimized for large inputs.

[kovatz]

Thanks to solve the problem

[mah-shamim]

Thanks