Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Jump Game VI
Bookmark
Brute Force DP
DP + Heap
Monotonic Deque
Input
Example 1
Example 2
Example 3
Custom
nums
=
[1, -1, -2, 4, -7, 3]
,
k
=
2
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
dp
1
dp[i] = nums[i] + max(dp[i−k .. i−1]) — scan the window
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
dp
1
dp[i] = nums[i] + max(dp[i−k .. i−1]) — scan the window
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
1
process i =
1
scan dp[
0..0
]
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
1
0
process i =
2
scan dp[
0..1
]
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
1
0
scan
windowMax =
1
windowMax = max(…, dp[1]) =
1
at index 0
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
1
0
-1
process i =
3
scan dp[
1..2
]
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
window max
1
0
-1
4
windowMax =
0
dp[3] =
4
+
0
=
4
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
1
0
-1
4
scan
windowMax =
-1
windowMax = max(…, dp[2]) =
-1
at index 2
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
window max
1
0
-1
4
-3
windowMax =
4
dp[4] =
-7
+
4
=
-3
i
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
window ≤ 2
dp
1
0
-1
4
-3
scan
windowMax =
4
windowMax = max(…, dp[4]) =
4
at index 3
nums
1
-1
-2
4
-7
3
0
1
2
3
4
5
dp
1
0
-1
4
-3
7
return dp[5] =
7
algo
master
.
io
Step:
Start: dp[i] = nums[i] + max(dp[i-k .. i-1]). Scan each window for its max.
0 / 21
Input
Example 1
Example 2
Example 3
Custom
nums
=
[1, -1, -2, 4, -7, 3]
,
k
=
2
0 / 21
algo
master
.
io
Step:
Start: dp[i] = nums[i] + max(dp[i-k .. i-1]). Scan each window for its max.
