Watch 10 video solutions for Maximum Array Hopping Score II, a medium level problem involving Array, Stack, Greedy. This walkthrough by NeetCode has 605,143 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array nums, you have to get the maximum score starting from index 0 and hopping until you reach the last element of the array.
In each hop, you can jump from index i to an index j > i, and you get a score of (j - i) * nums[j].
Return the maximum score you can get.
Example 1:
Input: nums = [1,5,8]
Output: 16
Explanation:
There are two possible ways to reach the last element:
0 -> 1 -> 2 with a score of (1 - 0) * 5 + (2 - 1) * 8 = 13.0 -> 2 with a score of (2 - 0) * 8 = 16.Example 2:
Input: nums = [4,5,2,8,9,1,3]
Output: 42
Explanation:
We can do the hopping 0 -> 4 -> 6 with a score of (4 - 0) * 9 + (6 - 4) * 3 = 42.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: You start at index 0 in an array and can jump to any later index j > i. A jump from i to j adds (j - i) * nums[i] to your score. The goal is to reach the last index while maximizing the total score. The challenge is choosing jump boundaries that maximize the contribution from each position.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
The most direct idea is dynamic programming. Let dp[i] represent the maximum score obtainable starting from index i. For each index, iterate over every possible next position j > i and compute (j - i) * nums[i] + dp[j]. Take the maximum of all choices. This approach is straightforward and clearly models the problem, but the nested iteration leads to O(n²) time complexity, which becomes too slow for large inputs.
Approach 2: Greedy + Monotonic Stack (O(n) time, O(n) space)
The optimal solution uses a greedy observation with a monotonic stack. If a future index has a larger or equal value, it is usually better to jump there because the multiplier nums[i] stays fixed while the distance grows. Instead of checking every possible destination, maintain a decreasing stack of indices while scanning from right to left. The stack keeps candidate positions that yield better long-term scores.
For each index i, pop smaller values from the stack since they will never produce a better continuation than a larger future value. The next index remaining on the stack becomes the optimal next hop. The score contribution is computed using (next - i) * nums[i] plus the stored result from that position. This reduces repeated comparisons and guarantees each index is pushed and popped at most once.
The technique combines ideas from array traversal, stack processing, and greedy selection. Because every element enters and leaves the stack once, the total complexity becomes O(n) time with O(n) auxiliary space.
Recommended for interviews: Start by explaining the O(n²) dynamic programming formulation to show you understand the scoring transition. Then optimize using a greedy insight with a monotonic stack. Interviewers typically expect the linear solution because it demonstrates pattern recognition with monotonic structures and the ability to eliminate redundant comparisons.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Jump Enumeration | O(n²) | O(1) | Useful for understanding the scoring rule and verifying small inputs |
| Dynamic Programming | O(n²) | O(n) | Clear state transition; good starting point before optimization |
| Greedy + Monotonic Stack | O(n) | O(n) | Optimal solution for large arrays; removes redundant jump checks |