Sliding Window — Jump Game VI
↗ LeetCode: Jump Game VI · Medium · pattern chapter →
Start at 0. At index i, jump 1..k steps. Max total score reaching last index.
Example 1 — nums=[1,-1,-2,4,-7,3], k=2 → 7Example 2 — nums=[10,-5,-2,4,0,3], k=3 → 17Example 3 — nums=[1,-5,-20,4,-1,3,-6,-3], k=2 → 0
Constraints — 1 ≤ n ≤ 10⁵; 1 ≤ k ≤ n. Naive DP is O(nk) — at n=k=10⁵ that's 10¹⁰ ops (~5 min). Deque brings it to O(n).
Interview timer00:00
Approach 1 — Brute DP with inner window scan
Intuition. dp[i] = nums[i] + max(dp[i-k..i-1]). For each i, scan back k positions.
int maxResultBrute(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
int mx = Integer.MIN_VALUE;
for (int j = Math.max(0, i - k); j < i; j++) mx = Math.max(mx, dp[j]);
dp[i] = nums[i] + mx;
}
return dp[n - 1];
}Complexity — Time O(nk); Space O(n). TLE at 10⁵. In an interview say "sliding max = monotonic deque, one canonical template."
Approach 2 — DP + monotonic deque (canonical)
Insight. The inner scan is a window-max. Maintain a deque of indices with decreasing dp values; front is always the current window max.
int maxResult(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
Deque<Integer> dq = new ArrayDeque<>();
dq.offerLast(0);
for (int i = 1; i < n; i++) {
if (dq.peekFirst() < i - k) dq.pollFirst();
dp[i] = nums[i] + dp[dq.peekFirst()];
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
dq.offerLast(i);
}
return dp[n - 1];
}Complexity — Time O(n); Space O(n). Say aloud in an interview: "same monotonic-deque template as Sliding Window Maximum and Constrained Subsequence Sum."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute DP (window scan) | O(nk) | O(n) | Reference; TLE at 10⁵ |
| Deque DP | O(n) | O(n) | Canonical |
When to use which
- DP with window-max transition → monotonic deque.
- "Min steps" → BFS layers instead.
- k=∞ (unbounded) → prefix max is enough.