Problem Breakdown
We need to find two indices i and j such that . The goal is to maximize the score defined by:
Inputs: An integer array values of length at least 2.
Outputs: A single integer representing the maximum possible score.
Implicit Constraints & Edge Cases:
- Indices: We must strictly enforce . This means we cannot pair an element with itself or a previous index as the second part of the pair if it violates order (though mathematically handled by iteration direction).
- Values: Values are positive ( to ), but indices can be up to 50,000. The term is always negative or zero since . This means the distance penalty reduces the score significantly as elements get further apart.
- Overflow: With values and length , the maximum possible sum fits comfortably within a standard 32-bit integer, but Python handles arbitrary precision integers anyway. No special overflow handling needed in Python.
Intuition
A naive approach would be to iterate through all pairs and calculate the score for each pair.
- Brute Force Complexity: . With , this results in roughly operations, which will exceed time limits (typically ops/sec).
Key Insight: Variable Separation.
Let’s rearrange the score formula to separate terms dependent on i and terms dependent on j:
Notice that for a fixed current index acting as j, we want to maximize the first part among all valid previous indices .
The second part is constant once we are at index j.
Optimal Strategy:
As we iterate through the array from left to right, every element can act as a potential candidate for position i (the first spot) or position j (the second spot). We maintain a running maximum of seen so far. When we reach index j, we calculate the score using that stored maximum and update our global result.
Approach
- Initialize a variable, say
max_i_val, to store for all valid . Start with index 0:max_i_val = values[0]. - Initialize
ans(maximum score found so far) to the smallest possible integer or calculate it using the first pair explicitly if needed. A safe initialization is negative infinity. - Iterate through the array starting from index .
- At each step:
- Calculate potential current score:
current_score = max_i_val + values[j] - j. - Update global maximum:
ans = max(ans, current_score). - Prepare for next iteration by updating the best first element seen so far:
max_i_val = max(max_i_val, values[j] + j). Note that we update this using because in future iterations (where new index is ), the current can become a valid candidate for position .
- Calculate potential current score:
- Return
ansafter loop completion.
Complexity Analysis
- Time Complexity: , where is the length of
values. We traverse the array exactly once with constant-time operations inside the loop. - Space Complexity: . We only use a few integer variables regardless of input size.
Edge Cases Handled
- Minimum Length: The code handles
len(values) == 2correctly by initializing with index 0 and iterating starting at index 1 (one iteration). - Decreasing Values: If values decrease rapidly, the distance penalty might outweigh value gains. The algorithm naturally selects pairs that balance this trade-off via
max_i_val. - Single Valid Pair: Since we initialize with logic and loop from 1, if only one pair exists (array size 2), it calculates exactly once before returning.
Solution
from typing import List
def maxScoreSightseeingPair(values: List[int]) -> int:
# Constraints guarantee len(values) >= 2
# Initialize best_i_val with values[0] + 0 (i=0 case for the first element)
max_i_val = values[0]
ans = float('-inf')
for j in range(1, len(values)):
# Calculate score using the best previous 'i' and current 'j'
# Formula rearranged: (values[i] + i) + (values[j] - j)
current_score = max_i_val + values[j] - j
if current_score > ans:
ans = current_score
# Update the best candidate for position 'i' seen so far.
# Current index 'j' can now be an 'i' for future indices acting as 'k'.
val_plus_idx = max_i_val + (values[j] - values[0]) if False else 0
# Correct logic update: compare current j's potential i-value with stored best
candidate_next_i = values[j] + j
if candidate_next_i > max_i_val:
max_i_val = candidate_next_i
return ans
# Alternative concise implementation using Python's built-in functions logic implicitly,
# but the explicit loop above is clearer for interview explanation.