Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Best Time to Buy and Sell Stock IV
Bookmark
Memoization
1D DP
Input
k=2, small
k=2, standard
k=1
k=3
Custom
k
=
2
,
prices
=
[2, 4, 1]
prices
k =
2
2
day 0
4
day 1
1
day 2
stack
-
memo
Start: at most 2 buy/sell transactions on prices = [2, 4, 1]
prices
k =
2
2
day 0
4
day 1
1
day 2
stack
-
memo
Start: at most 2 buy/sell transactions on prices = [2, 4, 1]
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,0,free)
memo
Day 1 is still in range.
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,0,free) (2,0,free) (3,0,free)
memo
Past the last day: nothing left to earn.
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,0,free)
memo
2,0,0:0
best from here =
0
Skip day 1: the rest is worth 0.
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,0,free) (2,1,hold)
memo
2,0,0:0
best from here =
0
Skip day 2: the rest is worth 0.
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,0,free)
memo
2,0,0:0
2,1,1:1
1,0,0:0
best from here =
0
Store (1, 0, 0) = 0 and return it.
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,1,hold) (2,1,hold)
memo
2,0,0:0
2,1,1:1
1,0,0:0
Day 2 is still in range.
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,1,hold) (2,1,free)
memo
2,0,0:0
2,1,1:1
1,0,0:0
Is (2, 1, 0) already solved?
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
(0,0,free) (1,1,hold) (2,1,free)
memo
2,0,0:0
2,1,1:1
1,0,0:0
best from here =
0
Buy on day 2 for 1: -1, worse than skipping.
prices
k =
2
2
day 0
4
day 1
1
day 2
i
stack
-
memo
2,0,0:0
2,1,1:1
1,0,0:0
2,1,0:0
1,1,1:4
0,0,0:2
Done! Best profit with at most 2 transactions = 2 (13 calls, 1 cache hits)
answer = sell[2] =
2
algo
master
.
io
Step:
Start: at most 2 buy/sell transactions on prices = [2, 4, 1]
0 / 54
Input
k=2, small
k=2, standard
k=1
k=3
Custom
k
=
2
,
prices
=
[2, 4, 1]
0 / 54
algo
master
.
io
Step:
Start: at most 2 buy/sell transactions on prices = [2, 4, 1]
