Problem Description

You are given an array nums and need to find the maximum score you can achieve by jumping through the array.

Starting from index 0, you can make "hops" to reach the last element of the array. In each hop, you can jump from your current index i to any index j where j > i. When you make such a jump, you earn a score of (j - i) * nums[j].

Your goal is to find the maximum total score you can accumulate by making a sequence of jumps from index 0 to the last index of the array.

For example, if you're at index i and jump to index j, you gain (j - i) * nums[j] points. The distance you jump (j - i) is multiplied by the value at your destination nums[j]. You continue making jumps until you reach the final index, and the sum of all scores from your jumps is your total score.

The challenge is to determine which sequence of jumps will give you the maximum possible total score.

Intuition

When we're at any position i, we need to decide where to jump next. The score for jumping to position j is (j - i) * nums[j]. This means we get more points by either jumping further (larger j - i) or jumping to a position with a higher value (larger nums[j]).

Let's think about when we would want to jump to a particular position. If we're at position i and considering positions ahead, we should ask: "Is there a better position to jump to later?"

Consider two positions j1 and j2 where i < j1 < j2. If nums[j1] <= nums[j2], would we ever want to jump to j1? The answer is no! Here's why:

• If we jump directly to j2, we get score (j2 - i) * nums[j2]
• If we jump to j1 first then j2, we get (j1 - i) * nums[j1] + (j2 - j1) * nums[j2]

The direct jump gives us (j2 - i) * nums[j2] while the two-hop path gives us (j1 - i) * nums[j1] + (j2 - j1) * nums[j2]. Since nums[j1] <= nums[j2], we can see that replacing nums[j1] with nums[j2] in the first term would only increase our score. This means the direct jump is always better or equal.

This insight tells us that we should only consider jumping to positions that have no greater or equal value ahead of them. In other words, we only jump to positions that form a decreasing sequence when viewed from right to left.

This naturally leads to using a monotonic decreasing stack. As we traverse the array, we maintain positions whose values are strictly decreasing. When we encounter a new position with a value greater than or equal to the stack top, we remove the stack top because it's no longer a candidate for jumping to - we'd rather jump to this new, better position instead.

The positions that remain in our stack at the end represent the optimal jumping points that will maximize our score.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

We implement the solution using a monotonic stack to identify the optimal jumping positions.

Building the Monotonic Stack:

We traverse the array nums from left to right, maintaining a stack stk that stores indices of elements in a monotonically decreasing order (based on their values).

For each position i with value nums[i]:

• While the stack is not empty and nums[stk[-1]] <= nums[i], we pop the top element from the stack
• After popping all smaller or equal elements, we push index i onto the stack

This process ensures that the stack contains indices of elements that form a strictly decreasing sequence. These are the positions we should jump to for maximum score.

Calculating the Maximum Score:

After building the stack, we have identified all optimal jumping positions. Now we calculate the total score:

1. Initialize ans = 0 (to store the total score) and i = 0 (current position)
2. For each index j in the stack (from bottom to top):
   • Add the score for jumping from position i to position j: ans += nums[j] * (j - i)
   • Update current position: i = j

The algorithm works because:

• The stack contains positions in increasing order of indices (since we pushed them left to right)
• Each position in the stack represents an optimal jump destination
• We jump to these positions sequentially, accumulating the maximum possible score

Time Complexity: O(n) where n is the length of the array, as each element is pushed and popped from the stack at most once.

Space Complexity: O(n) for storing the stack in the worst case when the array is strictly decreasing.

Example Walkthrough

Let's walk through the solution with the array nums = [1, 3, 1, 5].

Step 1: Build the Monotonic Decreasing Stack

We traverse the array from left to right, maintaining indices whose values form a strictly decreasing sequence:

• i = 0, nums[0] = 1: Stack is empty, push 0. Stack: [0]
• i = 1, nums[1] = 3: Compare with stack top: nums[0] = 1 <= 3, so pop 0. Stack becomes empty, then push 1. Stack: [1]
• i = 2, nums[2] = 1: Compare with stack top: nums[1] = 3 > 1, so just push 2. Stack: [1, 2]
• i = 3, nums[3] = 5: Compare with stack top: nums[2] = 1 <= 5, so pop 2. Stack: [1]. Compare again: nums[1] = 3 <= 5, so pop 1. Stack becomes empty, then push 3. Stack: [3]

Final stack: [3]

Step 2: Calculate Maximum Score

Now we jump through the positions in our stack:

• Start at position i = 0
• Jump to position j = 3 (the only element in our stack)
• Score for this jump: (3 - 0) * nums[3] = 3 * 5 = 15

Total maximum score: 15

Why is this optimal?

Let's verify by checking other possible paths:

• Path 1: 0 → 3 gives score 3 * 5 = 15 ✓ (our solution)
• Path 2: 0 → 1 → 3 gives score 1 * 3 + 2 * 5 = 3 + 10 = 13
• Path 3: 0 → 2 → 3 gives score 2 * 1 + 1 * 5 = 2 + 5 = 7
• Path 4: 0 → 1 → 2 → 3 gives score 1 * 3 + 1 * 1 + 1 * 5 = 3 + 1 + 5 = 9

Our algorithm correctly identified that jumping directly to position 3 yields the maximum score of 15. The key insight is that since nums[3] = 5 is the largest value and appears at the end, we want to maximize the distance multiplier by jumping to it directly from the start.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

• The first loop iterates through each element in nums exactly once with index i from 0 to n-1.
• Inside this loop, the while loop might pop elements from the stack. However, each element can be pushed onto the stack at most once and popped at most once throughout the entire execution. Therefore, the total number of push and pop operations across all iterations is at most 2n.
• The second loop iterates through the elements in stk, which contains at most n elements (in the worst case when the array is strictly increasing).
• Overall, the total operations are bounded by O(n) + O(n) = O(n).

Space Complexity: O(n) where n is the length of the input array nums.

• The stack stk stores indices of elements from the input array.
• In the worst case (when the input array is strictly increasing), all n indices will be stored in the stack.
• Additional variables ans, i, and j use constant space O(1).
• Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Jump Mechanics

The Problem: Many developers initially interpret this as finding the maximum value we can achieve by jumping to the last index in one sequence. They might think we need to reach the last index and stop there, similar to classic jump game problems.

Why It Happens: The problem statement mentions "reaching the last element" which can be misleading. In reality, we're accumulating scores from all jumps, and the last jump destination doesn't have to be the final array element.

The Fix: Recognize that the monotonic stack identifies ALL positions that contribute to the maximum score. The algorithm naturally handles the entire array range, and the last element in the stack effectively represents the "dominant" element for the remaining portion of the array.

Pitfall 2: Using Non-Strict Inequality in Stack Comparison

The Problem: Using nums[monotonic_stack[-1]] < current_value instead of nums[monotonic_stack[-1]] <= current_value when popping from the stack.

# Incorrect - keeps equal values in stack
while monotonic_stack and nums[monotonic_stack[-1]] < current_value:
    monotonic_stack.pop()

# Correct - removes equal values too
while monotonic_stack and nums[monotonic_stack[-1]] <= current_value:
    monotonic_stack.pop()

Why It Matters: If we keep equal values in the stack, we might jump to positions with the same value unnecessarily. Since jumping further with the same value gives a better score (j-i) * nums[j], we should always prefer the rightmost occurrence of any value.

Example: For array [1, 3, 3, 5], keeping both index 1 and 2 (both have value 3) would be suboptimal. We should only keep index 2.

Pitfall 3: Incorrect Score Calculation Range

The Problem: Forgetting to update the previous_index or incorrectly calculating the range that each element "dominates."

# Incorrect - using wrong range calculation
for current_stack_index in monotonic_stack:
    contribution = nums[current_stack_index] * current_stack_index  # Wrong!
    total_score += contribution

# Correct - each element dominates from previous position to its position
for current_stack_index in monotonic_stack:
    contribution = nums[current_stack_index] * (current_stack_index - previous_index)
    total_score += contribution
    previous_index = current_stack_index

Why It Matters: Each element in the monotonic stack represents the best jump destination for a range of starting positions. The score contribution should be based on how many positions can optimally jump to this element, not just its absolute index.

Pitfall 4: Attempting Dynamic Programming First

The Problem: Trying to solve with DP by defining dp[i] as the maximum score to reach index i.

# Inefficient O(n²) approach
dp = [0] * len(nums)
for j in range(1, len(nums)):
    for i in range(j):
        dp[j] = max(dp[j], dp[i] + (j - i) * nums[j])

Why It's Suboptimal: While this works, it has O(n²) time complexity. The monotonic stack solution elegantly reduces this to O(n) by recognizing that we only need to consider "dominant" elements that form a decreasing sequence.

The Insight: The key observation is that if nums[j] >= nums[k] for j < k, we would never want to jump to position j instead of position k from any position i < j, because (k-i) * nums[k] >= (j-i) * nums[j] when nums[k] >= nums[j].