We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Best Sightseeing Pair

Number: 1063

Difficulty: Medium

Paid? No

Companies: Google, Meta, Bloomberg, Wayfair

Problem Description

Given an array of integers, where each integer represents the value of a sightseeing spot, we need to determine the maximum score for a pair of sightseeing spots. The score of a pair (i, j) with i < j is calculated as values[i] + values[j] + i - j. The task is to return the maximum score obtainable.

Key Insights

  • The score can be reformulated as (values[i] + i) + (values[j] - j), decoupling the contributions from the two indices.
  • While iterating through the array, maintain the maximum value of (values[i] + i) seen so far.
  • For every new spot j, combine the previously stored maximum with (values[j] - j) to update the answer.
  • This one-pass strategy ensures an O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves a single pass through the array, maintaining a variable (best_left) to record the maximum value of (values[i] + i) encountered so far. For each index j (starting from 1), calculate the score by adding best_left and (values[j] - j). Update the max score whenever a higher score is found, and also update the best_left for future calculations. This efficient approach leverages dynamic programming by keeping track of cumulative optimal sub-results.

Code Solutions

def maxScoreSightseeing(values):
    # best_left holds the maximum value of (values[i] + i) encountered up to the current index
    best_left = values[0] + 0  # Initialize with the first element and index
    max_score = 0  # Track the maximum score

    # Iterate through the array starting from the second element
    for j in range(1, len(values)):
        # Calculate current score using the best value so far and the current spot's contribution
        current_score = best_left + values[j] - j
        # Update max_score if the current score is greater
        max_score = max(max_score, current_score)
        # Update best_left with the maximum of itself and (values[j] + j)
        best_left = max(best_left, values[j] + j)
    return max_score

# Example usage:
print(maxScoreSightseeing([8, 1, 5, 2, 6]))  # Expected output: 11
← Back to All Questions