Maximum Array Hopping Score II - Solution & Explanation
Problem Statement
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 -> 2with a score of(1 - 0) * 5 + (2 - 1) * 8 = 13.0 -> 2with 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] <= 105
Approach Overview
Problem 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.
Solution
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.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,143 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Array Hopping Score II easy or hard?
Maximum Array Hopping Score II Python/Java solution
How to solve Maximum Array Hopping Score II in O(n)?
What is the best approach for Maximum Array Hopping Score II?
Is Maximum Array Hopping Score II asked at Google/Amazon/Meta?
What data structure is used in Maximum Array Hopping Score II?
What is the time complexity of Maximum Array Hopping Score II?
Ready to solve this problem?
Practice Maximum Array Hopping Score II with our built-in code editor and test cases.
Practice on FleetCode