360. Jump Game VI

dp[i] = best score to reach i = nums[i] + max(dp[i-k..i-1]). The inner max over a sliding window of size k is the classic monotonic-deque trick: keep indices whose dp is decreasing, drop ones that fell out of the window, and the front is always the window maximum.

The DP

Let dp[i] be the maximum score to arrive at index i. You must have jumped from some index in [i-k, i-1], so:

dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1])

with dp[0] = nums[0]. Done naively the inner max costs O(k) per index → O(nk).

Sliding-window maximum with a deque

Maintain a deque of indices whose dp values are decreasing from front to back. Then dp[deque.front] is always the maximum over the current window:

for i in 1..n-1:
    while deque.front < i - k: pop front      # slid out of the window
    dp[i] = dp[deque.front] + nums[i]         # front = window max
    while dp[deque.back] <= dp[i]: pop back    # i dominates weaker tails
    push i to the back

Each index is pushed and popped at most once → O(n) overall. The answer is dp[n-1].

Worked example

nums = [1, -1, -2, 4, -7, 3], k = 2. dp[0] = 1.

• i=1: window {0}. dp[1] = 1 + (-1) = 0.
• i=2: window {0,1}, max dp is dp[0]=1. dp[2] = 1 + (-2) = -1.
• i=3: window {1,2}, max dp is dp[1]=0. dp[3] = 0 + 4 = 4.
• i=4: window {2,3}, max dp is dp[3]=4. dp[4] = 4 + (-7) = -3.
• i=5: window {3,4}, max dp is dp[3]=4. dp[5] = 4 + 3 = 7.

Answer dp[5] = 7.

Complexity

• Time: O(n) — each index enters and leaves the deque once.
• Space: O(n) for dp (O(k) for the deque).

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        // deque holds indices with decreasing dp; front is the window maximum.
        Deque<Integer> dq = new ArrayDeque<>();
        dq.offerLast(0);
        for (int i = 1; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
            dp[i] = dp[dq.peekFirst()] + nums[i];
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
            dq.offerLast(i);
        }
        return dp[n - 1];
    }
}