Maximum Array Hopping Score I

Maximum Array Hopping Score I

What is this problem about?

In the Maximum Array Hopping Score I problem, you are given an array of integers representing scores. You start at index 0 and must hop to the end of the array (the last index). You can hop from index i to any index j where j > i. The score for a single hop is calculated as (j - i) * arr[j]. Your goal is to find the maximum total score you can achieve by the time you reach the end.

Why is this asked in interviews?

This is a Dynamic Programming and optimization problem. Interviewers ask it to test whether a candidate can transition from an $O(N^2)$ exhaustive search to an elegant $O(N)$ greedy or stack-based solution. It tests your mathematical intuition: if you jump to a smaller number, are you sacrificing a larger multiplier that could have been achieved by jumping directly to a larger number further down the line?

Algorithmic pattern used

While you can use 1D Dynamic Programming (dp[j] = max(dp[i] + (j-i)*arr[j])), the most optimal pattern is using a Monotonic Stack or a Suffix Maximum Array (Greedy). Because the score is strictly based on the destination value, you only ever want to hop to the absolute largest value available to the right of your current position. If there are multiple identical largest values, you want to hop to the furthest one to maximize the (j - i) distance multiplier.

1. Create a suffix_max array that stores the index of the maximum value from i to the end of the array.
2. Start at index 0. Look at suffix_max[1]. That index j is your optimal next hop.
3. Calculate the score, move your current position to j, and repeat until you reach the end.

Example explanation

Array: [1, 5, 2, 4, 3]. Length 5. End is index 4. Suffix max indices (from right to left):

• from 4: max is 3 (idx 4)
• from 3: max is 4 (idx 3)
• from 2: max is 4 (idx 3)
• from 1: max is 5 (idx 1)
• from 0: max is 5 (idx 1)

Hop sequence:

• Start at 0. Best hop is to suffix_max[1] which is index 1 (value 5).
• Hop to idx 1. Score = (1 - 0) * 5 = 5.
• Current at 1. Best hop is to suffix_max[2] which is index 3 (value 4).
• Hop to idx 3. Score = (3 - 1) * 4 = 8.
• Current at 3. Best hop is to suffix_max[4] which is index 4 (value 3).
• Hop to idx 4. Score = (4 - 3) * 3 = 3. Total Score = 5 + 8 + 3 = 16.

Common mistakes candidates make

A common error is writing the $O(N^2)$ DP solution dp[i] = Math.max(dp[i], dp[j] + (i-j)*arr[i]). For arrays of length $10^5$, this will Time Limit Exceed. Another mistake is hopping to the first instance of a maximum value instead of the last instance. Because the formula uses (j - i), hopping further to an identical value yields a strictly larger score.

Interview preparation tip

When tackling "hoppping" or "jump game" problems where the reward is multiplied by the distance, the Greedy Suffix Max pattern is almost always the intended optimal solution. Practice traversing an array backwards to track the index_of_max_seen_so_far. This $O(N)$ precomputation instantly builds the exact optimal path for you to follow on your forward pass.