Watch 10 video solutions for Maximum Array Hopping Score I, a medium level problem involving Array, Dynamic Programming, Stack. 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 <= 1031 <= nums[i] <= 105Problem Overview: You start at index 0 in an array and can jump to any later index j > i. Each jump from i to j contributes a score of (j - i) * nums[j]. The goal is to reach the last index while maximizing the total score. The challenge is choosing the best next index so future jumps also remain optimal.
Approach 1: Memoization Search (DFS + DP) (Time: O(n²), Space: O(n))
This approach models the problem as a recursive decision process. From each index i, iterate over every possible next position j where j > i. The score for choosing j is (j - i) * nums[j] + dfs(j). Cache results with memoization so each starting index is computed once. The key idea is that the best result from index i only depends on the best results of later indices. Although this uses dynamic programming with caching to avoid recomputation, the nested exploration still results in O(n²) time in the worst case. It works well for understanding the state transition and verifying correctness before optimizing.
Approach 2: Dynamic Programming with Monotonic Stack (Time: O(n), Space: O(n))
The quadratic transition can be optimized by observing how the jump score behaves. Since the contribution includes (j - i) multiplied by nums[j], larger values of nums[j] dominate smaller ones for future jumps. Instead of checking every j, maintain a candidate set of indices using a monotonic stack. Process the array from right to left and compute dp[i], the best score starting at index i. The stack keeps indices whose values produce better transitions for earlier positions. When a new index is processed, remove dominated candidates and calculate the optimal next jump using the top of the stack. Each index is pushed and popped at most once, giving linear time complexity. This pattern combines array traversal with a greedy candidate structure to eliminate unnecessary comparisons.
Recommended for interviews: Start by describing the memoized DFS or bottom-up DP since it clearly shows the state definition dp[i] and the transition over all j > i. After establishing correctness, discuss the optimization using a monotonic stack to reduce the transition cost. Interviewers typically expect recognition of the DP state first, then the stack-based optimization that improves the runtime from O(n²) to O(n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Memoization Search (DFS + DP) | O(n²) | O(n) | Best for understanding the DP state and transition. Useful when first deriving the recurrence. |
| Dynamic Programming with Monotonic Stack | O(n) | O(n) | Optimal approach for large arrays. Eliminates quadratic transitions using a stack of candidate indices. |