Maximum Array Hopping Score I - 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 <= 1031 <= nums[i] <= 105
Approach Overview
Problem 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 1: Memoization Search
We design a function dfs(i), which represents the maximum score that can be obtained starting from index i. Therefore, the answer is dfs(0).
The execution process of the function dfs(i) is as follows:
We enumerate the next jump position j. Thus, the score that can be obtained starting from index i is (j - i) times nums[j], plus the maximum score that can be obtained starting from index j, making the total score (j - i) times nums[j] + dfs(j). We enumerate all possible j and take the maximum score.
To avoid redundant calculations, we use memoization search. We save the calculated value of dfs(i), so it can be directly returned next time.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Dynamic Programming
We can transform the memoization search from Solution 1 into dynamic programming.
Define f[j] as the maximum score that can be obtained starting from index 0 and ending at index j. Therefore, the answer is f[n - 1].
The state transition equation is:
$
f[j] = max_{0 leq i < j} { f[i] + (j - i) times nums[j] }
The time complexity is O(n^2), and the space complexity is O(n). Here, n$ is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Approach 3: Monotonic Stack
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.
Finally, return the answer ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Memoization Search | — |
| Dynamic Programming | — |
| Monotonic Stack | — |
Detailed Complexity Analysis
| 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. |
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 I easy or hard?
Maximum Array Hopping Score I Python/Java solution
How to solve Maximum Array Hopping Score I in O(n)?
What is the best approach for Maximum Array Hopping Score I?
Is Maximum Array Hopping Score I asked at Google/Amazon/Meta?
What data structure is used in Maximum Array Hopping Score I?
What is the time complexity of Maximum Array Hopping Score I?
Ready to solve this problem?
Practice Maximum Array Hopping Score I with our built-in code editor and test cases.
Practice on FleetCode