Problem Description

You have an array of integers nums and a maximum jump distance k. You start at index 0 and want to reach the last index of the array.

From any position i, you can jump forward to any position between i + 1 and min(n - 1, i + k). In other words, you can jump at most k steps forward, but you cannot jump outside the array boundaries.

As you jump through the array, you collect points. Your score is the sum of all values nums[j] at each index j that you land on during your journey (including the starting position at index 0 and the final position at index n - 1).

Your goal is to find the maximum possible score you can achieve by choosing the optimal jumping path from index 0 to index n - 1.

For example, if nums = [1, -1, -2, 4, -7, 3] and k = 2:

• You start at index 0 (score = 1)
• You could jump to index 1 or 2
• From there, continue jumping with the constraint of at most 2 steps forward
• You must eventually reach index 5
• The sum of all nums[j] values at positions you visit becomes your total score

The challenge is to find the jumping sequence that maximizes this total score.

Intuition

To find the maximum score, we need to think about this problem backwards. At each position i, we want to know: "What's the maximum score I can achieve to reach this position?"

Let's define f[i] as the maximum score when reaching index i. To reach position i, we must have come from some previous position j where j is within jumping distance (meaning i - k ≤ j ≤ i - 1). The score at position i would be the score at position j plus the value at position i.

This gives us the recurrence relation: f[i] = max(f[j]) + nums[i] for all valid j in range [i - k, i - 1].

The straightforward approach would be to check all possible previous positions for each index, but this would be inefficient with time complexity O(n * k).

The key optimization insight is that we're repeatedly finding the maximum value in a sliding window of size k. As we move from index i to i + 1, the window of valid previous positions slides forward by one position. This is a classic sliding window maximum problem.

We can maintain a monotonic deque to efficiently track the maximum value in the current window. The deque stores indices, and we maintain the property that the f values corresponding to these indices are in decreasing order. This way:

• The front of the deque always contains the index with the maximum f value in the current window
• When adding a new index, we remove all indices from the back that have smaller or equal f values (they'll never be useful)
• We remove indices from the front that are now outside the valid window (distance > k)

This optimization reduces the time complexity to O(n) since each index is added and removed from the deque at most once.

Learn more about Queue, Dynamic Programming, Monotonic Queue and Heap (Priority Queue) patterns.

Solution Approach

The solution implements dynamic programming with monotonic queue optimization. Let's walk through the implementation step by step:

1. Initialize the DP array and monotonic deque:

f = [0] * n  # f[i] stores maximum score to reach index i
q = deque([0])  # monotonic deque storing indices

The deque initially contains index 0 since we start there.

2. Process each position from left to right: For each index i from 0 to n-1:

3. Remove outdated indices from the deque front:

if i - q[0] > k:
    q.popleft()

If the index at the front of the deque is more than k steps away from current position i, it's no longer reachable in one jump, so we remove it.

4. Calculate the maximum score for position i:

f[i] = nums[i] + f[q[0]]

The front of the deque (q[0]) contains the index with the maximum f value among all valid previous positions. We add nums[i] to this maximum to get f[i].

5. Maintain the monotonic property of the deque:

while q and f[q[-1]] <= f[i]:
    q.pop()

Before adding index i to the deque, we remove all indices from the back whose f values are less than or equal to f[i]. These indices will never be optimal choices in the future because:

• Index i has a better (or equal) score
• Index i is more recent, so it will remain valid for longer

6. Add current index to the deque:

q.append(i)

7. Return the final result:

return f[-1]

The maximum score to reach the last index is stored in f[n-1].

Time Complexity: O(n) - Each index is added to and removed from the deque at most once.

Space Complexity: O(n) for the DP array, and O(k) for the deque (at most k+1 elements).

The monotonic deque ensures we can always find the maximum f value in the valid window in O(1) time by checking the front element, making this solution highly efficient.

Example Walkthrough

Let's walk through a small example with nums = [10, -5, -2, 4, 0, 3] and k = 3.

We want to find the maximum score jumping from index 0 to index 5, where we can jump at most 3 steps forward from any position.

Initial Setup:

• f = [0, 0, 0, 0, 0, 0] (will store max scores)
• q = deque([0]) (monotonic deque with indices)

Step 1: Process index 0

• No indices to remove (starting position)
• f[0] = nums[0] + 0 = 10
• q = deque([0])

Step 2: Process index 1

• Check if front index too far: 1 - 0 = 1 ≤ 3 ✓ (keep it)
• f[1] = nums[1] + f[0] = -5 + 10 = 5
• Compare with back of deque: f[0] = 10 > f[1] = 5, so keep index 0
• q = deque([0, 1])

Step 3: Process index 2

• Check if front index too far: 2 - 0 = 2 ≤ 3 ✓ (keep it)
• f[2] = nums[2] + f[0] = -2 + 10 = 8 (using max from front of deque)
• Compare with back: f[1] = 5 < f[2] = 8, remove index 1
• Compare with back: f[0] = 10 > f[2] = 8, keep index 0
• q = deque([0, 2])

Step 4: Process index 3

• Check if front index too far: 3 - 0 = 3 ≤ 3 ✓ (keep it)
• f[3] = nums[3] + f[0] = 4 + 10 = 14
• Compare with back: f[2] = 8 < f[3] = 14, remove index 2
• Compare with back: f[0] = 10 < f[3] = 14, remove index 0
• q = deque([3])

Step 5: Process index 4

• Check if front index too far: 4 - 3 = 1 ≤ 3 ✓ (keep it)
• f[4] = nums[4] + f[3] = 0 + 14 = 14
• Compare with back: f[3] = 14 = f[4] = 14, remove index 3
• q = deque([4])

Step 6: Process index 5

• Check if front index too far: 5 - 4 = 1 ≤ 3 ✓ (keep it)
• f[5] = nums[5] + f[4] = 3 + 14 = 17
• Final answer: f[5] = 17

Optimal Path: 0 → 3 → 5

• Start at index 0: collect 10
• Jump to index 3: collect 4
• Jump to index 5: collect 3
• Total score: 10 + 4 + 3 = 17

The monotonic deque efficiently maintained the maximum reachable score at each step, allowing us to compute the optimal solution in linear time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array once with a for loop from index 0 to n-1. Within each iteration:

• The popleft() operation occurs at most once per element (each element can only be removed from the front of the deque once)
• The f[i] = nums[i] + f[q[0]] operation takes O(1) time
• The while loop with pop() operations might seem like it could take O(n) time per iteration, but each element is added to the deque exactly once and removed at most once throughout the entire algorithm, amortizing to O(1) per iteration
• The append(i) operation takes O(1) time

Since each element is processed a constant number of times across all iterations, the total time complexity is O(n).

Space Complexity: O(n)

The algorithm uses:

• An array f of size n to store the dynamic programming results: O(n) space
• A deque q that can contain at most min(k+1, n) elements at any time: O(min(k+1, n)) space, which is O(n) in the worst case when k ≥ n-1

Therefore, the total space complexity is O(n).

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

Common Pitfalls

1. Forgetting to Handle the Starting Position Correctly

Pitfall: A common mistake is not properly initializing the DP for the starting position or trying to calculate dp[0] using the deque operations, which would fail since the deque might be empty or contain invalid indices.

Why it happens: The logic for positions 1 through n-1 involves looking back at previous positions, but position 0 has no previous positions to consider.

Solution: Ensure the deque is initialized with index 0 before the loop starts, and the DP calculation works correctly even for i=0:

# Correct initialization
deque_indices = deque([0])

# When i=0, the deque contains [0], so:
# dp[0] = nums[0] + dp[0] = nums[0] + 0 = nums[0]
# This correctly sets the starting position's score

2. Incorrect Window Size Check

Pitfall: Using the wrong condition to check if an index is outside the valid jump range:

# Wrong: doesn't account for the actual distance
if deque_indices[0] < i - k:  # This is off by one!
    deque_indices.popleft()

# Wrong: using length of deque instead of index difference  
if len(deque_indices) > k:
    deque_indices.popleft()

Why it happens: Confusion about whether to use < or <=, or misunderstanding that we need to check the distance between indices, not the deque size.

Solution: Use the correct condition that checks if the distance exceeds k:

# Correct: remove indices that are more than k steps away
if i - deque_indices[0] > k:
    deque_indices.popleft()

3. Maintaining Monotonic Property Incorrectly

Pitfall: Using strict inequality when maintaining the monotonic deque:

# Wrong: using strict inequality
while deque_indices and dp[deque_indices[-1]] < dp[i]:  # Should be <=
    deque_indices.pop()

Why it happens: Not realizing that keeping equal values would be redundant since the newer index with the same value is always preferable (it stays valid longer).

Solution: Use <= to remove indices with equal or smaller values:

# Correct: remove indices with smaller OR EQUAL dp values
while deque_indices and dp[deque_indices[-1]] <= dp[i]:
    deque_indices.pop()

4. Accessing Empty Deque

Pitfall: The deque might become empty after the window size check, leading to an IndexError when accessing deque_indices[0]:

# Dangerous if deque becomes empty
dp[i] = nums[i] + dp[deque_indices[0]]  # IndexError if deque is empty

Why it happens: Over-aggressive removal of elements or incorrect logic that empties the deque entirely.

Solution: The deque should never be empty in a correct implementation because:

• We always add the current index after processing
• We only remove indices outside the valid range
• For any position i, at least one previous position within range k should exist (except for i=0, which is handled by initialization)

However, for defensive programming:

# Defensive check (though shouldn't be necessary with correct logic)
if not deque_indices:
    dp[i] = nums[i]  # Handle edge case
else:
    dp[i] = nums[i] + dp[deque_indices[0]]