Maximum Array Hopping Score I solution and explanation
2 more videos on this problem
Weekly Contest 299 | Leetcode 2321 Maximum Score Of Spliced Array | DP | Kadane algorithmCoding Decoded · 14:14 · 1K views
2321. Maximum Score Of Spliced Array (Leetcode Hard)Programming Live with Larry · 9:49 · 741 views
Leetcode 2587: Rearrange Array to Maximize Prefix ScoreAlgorithms Casts · 8:57 · 344 views
The problem
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.
class Solution:
def maxScore(self, nums: List[int]) -> int:
@cache
def dfs(i: int) -> int:
return max(
[(j - i) * nums[j] + dfs(j) for j in range(i + 1, len(nums))] or [0]
)
return dfs(0)class Solution {
private Integer[] f;
private int[] nums;
private int n;
public int maxScore(int[] nums) {
n = nums.length;
f = new Integer[n];
this.nums = nums;
return dfs(0);
}
private int dfs(int i) {
if (f[i] != null) {
return f[i];
}
f[i] = 0;
for (int j = i + 1; j < n; ++j) {
f[i] = Math.max(f[i], (j - i) * nums[j] + dfs(j));
}
return f[i];
}
}class Solution {
public:
int maxScore(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
auto dfs = [&](this auto&& dfs, int i) -> int {
if (f[i]) {
return f[i];
}
for (int j = i + 1; j < n; ++j) {
f[i] = max(f[i], (j - i) * nums[j] + dfs(j));
}
return f[i];
};
return dfs(0);
}
};function maxScore(nums: number[]): number {
const n = nums.length;
const f: number[] = Array(n).fill(0);
const dfs = (i: number): number => {
if (f[i]) {
return f[i];
}
for (let j = i + 1; j < n; ++j) {
f[i] = Math.max(f[i], (j - i) * nums[j] + dfs(j));
}
return f[i];
};
return dfs(0);
}func maxScore(nums []int) int {
n := len(nums)
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if f[i] > 0 {
return f[i]
}
for j := i + 1; j < n; j++ {
f[i] = max(f[i], (j-i)*nums[j]+dfs(j))
}
return f[i]
}
return dfs(0)
}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.
class Solution:
def maxScore(self, nums: List[int]) -> int:
n = len(nums)
f = [0] * n
for j in range(1, n):
for i in range(j):
f[j] = max(f[j], f[i] + (j - i) * nums[j])
return f[n - 1]class Solution {
public int maxScore(int[] nums) {
int n = nums.length;
int[] f = new int[n];
for (int j = 1; j < n; ++j) {
for (int i = 0; i < j; ++i) {
f[j] = Math.max(f[j], f[i] + (j - i) * nums[j]);
}
}
return f[n - 1];
}
}class Solution {
public:
int maxScore(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
for (int j = 1; j < n; ++j) {
for (int i = 0; i < j; ++i) {
f[j] = max(f[j], f[i] + (j - i) * nums[j]);
}
}
return f[n - 1];
}
};function maxScore(nums: number[]): number {
const n = nums.length;
const f: number[] = Array(n).fill(0);
for (let j = 1; j < n; ++j) {
for (let i = 0; i < j; ++i) {
f[j] = Math.max(f[j], f[i] + (j - i) * nums[j]);
}
}
return f[n - 1];
}func maxScore(nums []int) int {
n := len(nums)
f := make([]int, n)
for j := 1; j < n; j++ {
for i := 0; i < j; i++ {
f[j] = max(f[j], f[i]+(j-i)*nums[j])
}
}
return f[n-1]
}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.
class Solution:
def maxScore(self, nums: List[int]) -> int:
stk = []
for i, x in enumerate(nums):
while stk and nums[stk[-1]] <= x:
stk.pop()
stk.append(i)
ans = i = 0
for j in stk:
ans += nums[j] * (j - i)
i = j
return ansclass Solution {
public int maxScore(int[] nums) {
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < nums.length; ++i) {
while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
stk.pop();
}
stk.push(i);
}
int ans = 0, i = 0;
while (!stk.isEmpty()) {
int j = stk.pollLast();
ans += (j - i) * nums[j];
i = j;
}
return ans;
}
}class Solution {
public:
int maxScore(vector<int>& nums) {
vector<int> stk;
for (int i = 0; i < nums.size(); ++i) {
while (stk.size() && nums[stk.back()] <= nums[i]) {
stk.pop_back();
}
stk.push_back(i);
}
int ans = 0, i = 0;
for (int j : stk) {
ans += (j - i) * nums[j];
i = j;
}
return ans;
}
};function maxScore(nums: number[]): number {
const stk: number[] = [];
for (let i = 0; i < nums.length; ++i) {
while (stk.length && nums[stk.at(-1)!] <= nums[i]) {
stk.pop();
}
stk.push(i);
}
let ans = 0;
let i = 0;
for (const j of stk) {
ans += (j - i) * nums[j];
i = j;
}
return ans;
}func maxScore(nums []int) (ans int) {
stk := []int{}
for i, x := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
i := 0
for _, j := range stk {
ans += (j - i) * nums[j]
i = j
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Memoization Search | – |
| Dynamic Programming | – |
| Monotonic Stack | – |
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. |
Frequently asked questions
Is Maximum Array Hopping Score I easy or hard?
Maximum Array Hopping Score I is rated Medium difficulty. The base dynamic programming idea is straightforward, but optimizing the transition using a monotonic stack requires deeper insight. Recognizing this pattern is the main challenge in interviews.
Maximum Array Hopping Score I Python/Java solution
Python and Java implementations typically build a dp array and iterate from right to left. A stack stores candidate indices for optimal jumps, and dp[i] is computed using the best candidate on the stack. The same logic translates directly to C++, Go, and TypeScript with O(n) time complexity.
How to solve Maximum Array Hopping Score I in O(n)?
Compute dp[i] from right to left where dp[i] represents the best score starting at index i. Maintain a monotonic stack of candidate jump positions that give better score contributions. Remove dominated indices and use the top candidate to compute dp[i]. Because each index is processed once, the algorithm runs in linear time.
What is the best approach for Maximum Array Hopping Score I?
The most efficient approach uses dynamic programming combined with a monotonic stack. Define dp[i] as the maximum score starting from index i and compute it from right to left. The stack keeps candidate indices that produce better jump scores, reducing the transition search. This optimization reduces the runtime from O(n²) to O(n).
Is Maximum Array Hopping Score I asked at Google/Amazon/Meta?
Problems combining dynamic programming with monotonic stacks are common in interviews at companies like Google, Amazon, and Meta. Variations of array hopping, jump optimization, and DP transition pruning frequently appear in technical screens. Understanding how to reduce O(n²) DP transitions to O(n) is a valuable interview skill.
What data structure is used in Maximum Array Hopping Score I?
The optimized solution uses a monotonic stack along with a dynamic programming array. The stack maintains candidate indices whose values produce better jump scores for earlier positions. This structure allows efficient pruning of dominated transitions during the DP computation.
What is the time complexity of Maximum Array Hopping Score I?
The optimized solution runs in O(n) time using dynamic programming with a monotonic stack, since each index is pushed and popped at most once. A straightforward memoized DFS or DP that checks every possible next index requires O(n²) time. Space complexity is O(n) for the DP array and stack.