The recurrence relation is: $dp[i] = nums[i] + \max(dp[i-k], dp[i-k+1], \dots, dp[i-1])$

Naive Pseudo-code

python
dp = array of size n
dp[0] = nums[0]

for i from 1 to n-1:
    max_prev = -infinity
    # Check the last k positions
    for j from 1 to k:
        if i - j >= 0:
            max_prev = max(max_prev, dp[i - j])
    dp[i] = nums[i] + max_prev

return dp[n-1]

Time Complexity Analysis

This approach has a time complexity of $O(N \cdot K)$. For every element i, we iterate up to k times backward. Given the constraints where $N \le 10^5$ and $K \le 10^5$, the total operations could reach $10^{10}$ in the worst case. This will result in a Time Limit Exceeded (TLE) error. We need a way to find the maximum in the range [i-k, i-1] faster than $O(K)$.

Core Insight for Jump Game VI

The core difficulty in the brute force approach is repeatedly scanning the previous k elements to find the maximum dp value. This is identical to the "Sliding Window Maximum" problem.

By maintaining a Monotonic Decreasing Queue (specifically a Deque), we can access the maximum value in the current window in $O(1)$ time.

The Deque stores indices of the dp array. We enforce an invariant where the values corresponding to these indices are strictly decreasing.

1. Front of Deque: Always holds the index of the maximum dp value in the current valid window [i-k, i-1].
2. Back of Deque: Used to maintain the monotonic property. When we compute a new dp[i], it might be larger than previous values. If dp[i] is larger than dp[back], the back index is useless (it is smaller and will expire sooner), so we remove it.

Visual Description: Imagine iterating through the array. As you calculate dp[i], you look at the front of the deque to get the best previous score. After calculating dp[i], you treat it as a candidate for future jumps. You insert i into the back of the deque. Before inserting, you pop any indices from the back that have a smaller dp value than dp[i]. This ensures the deque remains sorted by score descending. Finally, you check the front; if the index at the front is too old (outside the k range), you pop it.

Execution Flow

Let's trace nums = [1, -1, -2, 4, -7, 3] and k = 2.

1. Init: dp[0] = 1. Deque q = [0].
2. i = 1:
   • Window check: q.front() is 0. Valid since 0 >= 1 - 2.
   • Calc: dp[1] = nums[1] + dp[0] = -1 + 1 = 0.
   • Maintain: dp[1] (0) vs dp[q.back()] (1). 0 < 1, no pop.
   • Push 1. q = [0, 1].
3. i = 2:
   • Window check: q.front() is 0. Valid since 0 >= 2 - 2.
   • Calc: dp[2] = nums[2] + dp[0] = -2 + 1 = -1.
   • Maintain: dp[2] (-1) vs dp[q.back()] (0). -1 < 0, no pop.
   • Push 2. q = [0, 1, 2].
4. i = 3:
   • Window check: q.front() is 0. Invalid (0 < 3 - 2). Pop front. q is now [1, 2].
   • Calc: dp[3] = nums[3] + dp[1] = 4 + 0 = 4.
   • Maintain:
     • dp[3] (4) > dp[2] (-1). Pop 2. q = [1].
     • dp[3] (4) > dp[1] (0). Pop 1. q = [].
   • Push 3. q = [3].
5. i = 4:
   • Window check: q.front() is 3. Valid.
   • Calc: dp[4] = -7 + 4 = -3.
   • Maintain: -3 < 4. Push 4. q = [3, 4].
6. i = 5:
   • Window check: q.front() is 3. Valid.
   • Calc: dp[5] = 3 + 4 = 7.
   • Maintain: 7 > -3 (pop 4), 7 > 4 (pop 3). Push 5. q = [5].
7. End: Return dp[5] = 7.

Proof of Correctness

The algorithm relies on the principle of optimality in Dynamic Programming: the optimal path to index i is formed by extending the optimal path to some index j (where i-k <= j < i).

The correctness hinges on the Monotonic Deque correctly maintaining the maximum dp value in the sliding window.

1. Completeness: Since we remove indices only when they fall out of the window (< i-k) or are strictly smaller than a newer value, the largest valid value is always preserved.
2. Ordering: The deque is strictly decreasing. Therefore, the first element is always the maximum within the current window. Thus, dp[i] is always calculated using the true maximum of the preceding k states, ensuring the global maximum score is found.

Reference Implementation

C++ Solution for LeetCode 1696

cpp
#include <vector>
#include <deque>

using namespace std;

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        
        // Deque stores indices of potential max scores
        deque<int> dq;
        dq.push_back(0);
        
        for (int i = 1; i < n; ++i) {
            // 1. Remove indices that are out of the current window (i - k)
            if (!dq.empty() && dq.front() < i - k) {
                dq.pop_front();
            }
            
            // 2. The max score in the window is at the front of the deque
            dp[i] = nums[i] + dp[dq.front()];
            
            // 3. Maintain monotonicity: remove indices with scores <= current score
            while (!dq.empty() && dp[dq.back()] <= dp[i]) {
                dq.pop_back();
            }
            
            // 4. Add current index to the deque
            dq.push_back(i);
        }
        
        return dp[n - 1];
    }
};

Java Solution for LeetCode 1696

java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        
        // Deque stores indices, ordered by dp value descending
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offerLast(0);
        
        for (int i = 1; i < n; i++) {
            // 1. Remove indices out of window [i-k, i-1]
            if (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            
            // 2. Calculate dp[i] using the max from the window (front of deque)
            dp[i] = nums[i] + dp[deque.peekFirst()];
            
            // 3. Maintain monotonicity: remove elements smaller than current dp[i]
            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
                deque.pollLast();
            }
            
            // 4. Add current index
            deque.offerLast(i);
        }
        
        return dp[n - 1];
    }
}

Python Solution for LeetCode 1696

python
from collections import deque

class Solution:
    def maxResult(self, nums: list[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        
        # Deque stores indices
        q = deque([0])
        
        for i in range(1, n):
            # 1. Remove indices out of window
            if q[0] < i - k:
                q.popleft()
            
            # 2. Calculate current max score
            # q[0] is the index of the max score in the previous k steps
            dp[i] = nums[i] + dp[q[0]]
            
            # 3. Maintain Monotonicity (Decreasing)
            # Remove indices from back if their dp value is <= current dp[i]
            while q and dp[q[-1]] <= dp[i]:
                q.pop()
            
            # 4. Add current index
            q.append(i)
            
        return dp[n - 1]