Maximum Array Hopping Score II

Maximum Array Hopping Score II

What is this problem about?

This is the scaled-up version of Maximum Array Hopping Score I. You are given an array of integers and must start at index 0 and end at the last index. The score of a hop from i to j is (j - i) * arr[j]. You want to maximize the sum of all hop scores. The key difference in Part II is that the constraints are significantly larger, meaning any $O(N^2)$ DP approach is completely unviable and will fail immediately.

Why is this asked in interviews?

This problem is a strict enforcer of optimal array traversal. Interviewers use it to weed out candidates who rely solely on generic DP templates. It requires recognizing that the mathematical formula dictates a greedy approach. It tests whether a candidate can identify that intermediate hops to smaller numbers are mathematically inferior to a single long jump to a larger number.

Algorithmic pattern used

The absolute best approach is the Monotonic Stack or Suffix Maximum Array. As established in Part I, you should only ever jump to the largest element available to your right. If you use a Monotonic Stack from right to left, you can filter out all "sub-optimal" landing spots. Alternatively, building an array next_best_hop[i] by scanning backwards in $O(N)$ time allows you to simulate the optimal jumps in a second $O(N)$ forward pass.

Example explanation

Array: [3, 1, 4, 1, 5, 9, 2, 6, 5]. (Indices 0 to 8). We are at 0. We want to find the largest element to our right.

• The largest element in the entire array to the right of 0 is 9 at index 5.
• We jump directly from 0 to 5. Score = (5 - 0) * 9 = 45.
• We are at 5. The largest element to the right of 5 is 6 at index 7.
• We jump from 5 to 7. Score = (7 - 5) * 6 = 12.
• We are at 7. The largest element to the right is 5 at index 8.
• We jump from 7 to 8. Score = (8 - 7) * 5 = 5. Total = 45 + 12 + 5 = 62. Any other sequence of jumps (e.g., jumping to 4, then 5, then 9) will mathematically yield a smaller total score.

Common mistakes candidates make

The most frequent mistake in the Hard variation is using a 32-bit integer for the total score. Because the values can be large and the distances can be up to $10^5$, multiplying them and summing them up will easily cause a standard integer overflow, resulting in a negative or incorrect number. You must use a long (64-bit integer) to accumulate the final score.

Interview preparation tip

For the Maximum Array Hopping Score II coding problem, always declare your accumulator as long totalScore = 0;. Furthermore, when writing the Suffix Max logic, if two values are equal, you must prefer the one with the larger index. Make sure your backwards traversal uses >= instead of strictly > when comparing the current element to the running suffix maximum.