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.
We observe that for the current position i, we should jump to the next position j with the maximum value to obtain the maximum score.
Therefore, we traverse the array nums, maintaining a stack stk that is monotonically decreasing from the bottom to the top of the stack. For the current position i being traversed, if the value corresponding to the top element of the stack is less than or equal to nums[i], we continuously pop the top element of the stack until the stack is empty or the value corresponding to the top element of the stack is greater than nums[i], and then push i into the stack.
Next, we initialize the answer ans and the current position i = 0, traverse the elements in the stack, each time taking out the top element j, updating the answer ans += nums[j] times (j - i), and then updating i = j.
Python
Java
C++
Go
TypeScript
| 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 |
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,143 views views
Watch 9 more video solutions →Practice Maximum Array Hopping Score II with our built-in code editor and test cases.
Practice on FleetCode