101
0/320
Loading content...
You are planning a road trip through a scenic region and have access to a list of landmark ratings. Each landmark at position i has an associated attractiveness rating ratings[i]. The goal is to select two landmarks to visit—one at an earlier position and one at a later position along your route.
However, the total enjoyment from visiting any pair of landmarks diminishes based on the travel distance between them. Specifically, for a pair of landmarks at positions i and j (where i < j), the overall experience score is calculated as:
score = ratings[i] + ratings[j] - (j - i)
This formula represents the combined attractiveness of both landmarks, reduced by the distance penalty incurred while traveling from the first to the second.
Your task is to find the maximum possible experience score achievable by selecting any valid pair of landmarks.
Key Insight: The formula can be rearranged as (ratings[i] + i) + (ratings[j] - j), allowing you to separately maximize the contribution from the starting landmark and the destination landmark as you traverse the array.
ratings = [8,1,5,2,6]11Choosing landmarks at positions i = 0 and j = 2 gives: ratings[0] + ratings[2] + 0 - 2 = 8 + 5 - 2 = 11. This is the maximum achievable experience score.
ratings = [1,2]2The only possible pair is i = 0 and j = 1, giving: ratings[0] + ratings[1] + 0 - 1 = 1 + 2 - 1 = 2.
ratings = [5,7,4,3,2]11Choosing landmarks at positions i = 0 and j = 1 gives: ratings[0] + ratings[1] + 0 - 1 = 5 + 7 - 1 = 11. Despite having higher individual ratings elsewhere, the proximity of these two landmarks maximizes the total score.
Constraints