Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Constrained Subsequence Sum
Bookmark
Brute Force
DP + Heap
Monotonic Deque
Input
Standard
All Negative
Mixed
Custom
nums
=
[10, 2, -10, 5, 20]
,
k
=
2
result =
10
nums
10
2
-10
5
20
0
1
2
3
4
dp
10
dp[i] = nums[i] + max(0, max(dp[i−k .. i−1])); answer = max(dp)
result =
10
nums
10
2
-10
5
20
0
1
2
3
4
dp
10
dp[i] = nums[i] + max(0, max(dp[i−k .. i−1])); answer = max(dp)
result =
10
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
10
process i =
1
scan dp[
0..0
]
result =
12
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
10
12
result = max(result, dp[1]) =
12
new max
result =
12
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
10
12
scan
windowMax =
10
windowMax = max(…, dp[0]) =
10
at index 0
result =
12
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
window max
10
12
2
dp[2] =
-10
+ max(0,
12
) =
2
result =
12
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
10
12
2
scan
windowMax =
12
windowMax = max(…, dp[1]) =
12
at index 1
result =
12
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
window max
10
12
2
17
dp[3] =
5
+ max(0,
12
) =
17
result =
17
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
10
12
2
17
process i =
4
scan dp[
2..3
]
result =
17
i
nums
10
2
-10
5
20
0
1
2
3
4
window ≤ 2
dp
window max
10
12
2
17
37
dp[4] =
20
+ max(0,
17
) =
37
result =
37
nums
10
2
-10
5
20
0
1
2
3
4
dp
10
12
2
17
37
return max(dp) =
37
algo
master
.
io
Step:
Start: dp[i] = nums[i] + max(0, max(dp[i-k .. i-1])); answer is max(dp).
0 / 21
Input
Standard
All Negative
Mixed
Custom
nums
=
[10, 2, -10, 5, 20]
,
k
=
2
0 / 21
algo
master
.
io
Step:
Start: dp[i] = nums[i] + max(0, max(dp[i-k .. i-1])); answer is max(dp).
