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 III
Bookmark
Brute Force
Left / Right
State Machine
k Transactions
Input
Standard
Increasing
Decreasing
Complex
Custom
prices
=
[3, 3, 5, 0, 0, 3, 1, 4]
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
left[i]
right[i]
Start: cut the days at every split and solve one transaction on each side
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
left[i]
right[i]
Start: cut the days at every split and solve one transaction on each side
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
right[i]
4
best so far =
0
Best single transaction in days 0..7: sell high at 5, profit 4
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
right[i]
4
4
best so far =
4
Best single transaction in days 1..7: sell high at 5, profit 4
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
2
right[i]
4
4
best so far =
4
Best single transaction in days 0..2: buy low at 3, profit 2
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
2
2
right[i]
4
4
4
best so far =
6
Best single transaction in days 0..3: buy low at 0, profit 2
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
2
2
2
right[i]
4
4
4
4
best so far =
6
Best single transaction in days 0..4: buy low at 0, profit 2
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
2
2
2
3
right[i]
4
4
4
4
4
best so far =
6
Best single transaction in days 0..5: buy low at 0, profit 3
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
2
2
2
3
right[i]
4
4
4
4
4
3
best so far =
6
Split at day 6: days 0..6 on the left, days 6..7 on the right
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
2
2
2
3
3
right[i]
4
4
4
4
4
3
3
best so far =
6
Split at day 7: days 0..7 on the left, days 7..7 on the right
prices
3
day 0
3
day 1
5
day 2
0
day 3
0
day 4
3
day 5
1
day 6
4
day 7
i
left[i]
0
0
2
2
2
3
3
4
right[i]
4
4
4
4
4
3
3
0
Done! Best profit with at most 2 transactions = 6 (split at day 2)
answer = sell2 =
6
algo
master
.
io
Step:
Start: cut the days at every split and solve one transaction on each side
0 / 34
Input
Standard
Increasing
Decreasing
Complex
Custom
prices
=
[3, 3, 5, 0, 0, 3, 1, 4]
0 / 34
algo
master
.
io
Step:
Start: cut the days at every split and solve one transaction on each side
