Solution to LeetCode 121 Best Time to Buy and Sell Stock & LeetCode 122 Best Time to Buy and Sell Stock II & LeetCode 123 Best Time to Buy and Sell Stock III.
LeetCode 121
Best Time to Buy and Sell Stock (Easy) [link]
1] Dynamic Programming
Define dp[i][0] as the max profit when you have a stock on the ith day, and dp[i][1] as the max profit when you don’t have a stock on the ith day.
dp[i][0] can come from 1) dp[i-1][0] if you have the stock on the i-1th day; 2) -price[i] if you buy a stock on the ith day.
We want the max profit, so the recurrent relation is dp[i][0] = max(dp[i-1][0], -price[i]).
dp[i][1] can come from 1) dp[i-1][1] if you don’t have any stock on the i-1th day; 2) price[i]+dp[i-1][0] if you sell the stock on the ith day.
We want the max profit, so the recurrent relation is dp[i][1] = max(dp[i-1][1], price[i]+dp[i-1][0]).
The base case is dp[0][0]=-price[0] because you buy a stock on the first day, and dp[0][1]=0 because you don’t have any stock on the first day.
The result is dp[-1][1] because you have to sell the stock by the final day.
The time complexity is O(n). The space complexity is O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0]*2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,length):
dp[i][0] = max(dp[i-1][0], -prices[i]) # have stock
dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0]) # don't have stock
return dp[-1][1]
Since dp[i] only depends on dp[i-1], we can optimize the space complexity by applying rolling array. So the space complexity becomes O(1).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0]*2 for _ in range(2)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,length):
dp[i%2][0] = max(dp[(i-1)%2][0], -prices[i]) # have stock
dp[i%2][1] = max(dp[(i-1)%2][1], prices[i]+dp[(i-1)%2][0]) # don't have stock
return dp[(length-1)%2][1]
2] Greedy
Recurrence relation: dp[j] = max(dp[j-1], price[j] - min_{i<=j}(price(i)))
Base case: if no profit, then no transaction, return 0.
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
minprice = 10**9
ans = 0 # if profit is negative, then no transaction
for j in prices:
ans = max(j - minprice, ans)
minprice = min(j, minprice)
return ans
LeetCode 122
Best Time to Buy and Sell Stock II (Median) [link]
1] Dynamic Programming
Key: One stock can be bought and sold many times.
Define dp[i][0] as the max profit when you have a stock on the ith day, and dp[i][1] as the max profit when you don’t have a stock on the ith day.
dp[i][0] can come from 1) dp[i-1][0] if you have stock on the day before; 2) dp[i-1][1]-prices[i] if you have sold one and buy another one.
dp[i][1] can come from 1) dp[i-1][1] if you don’t have any stock on the day before; 2) dp[i-1][0]+prices[i] if you have had one and sold it on the ith day.
Time complexity O(n). Space complexity O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
return dp[-1][1]
Optimize space complexity to O(1) by apply rolling array.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(2)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-1)%2][1]-prices[i])
dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-1)%2][0]+prices[i])
return dp[(length-1)%2][1]
2] Greedy
Recurrence relation: dp[j] = max(dp[j-1], price[j] + max_i(dp[i] - price[i]))
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
n = len(prices)
ans = 0
balance = -10**9
for j in prices:
ans = max(ans, balance + j)
balance = max(balance, ans - j)
return ans
LeetCode 123
Best Time to Buy and Sell Stock III (Hard) [link]
Key: You may complete at most two transactions.
There can be five statues. 1) no action; 2) buy in for the first time; 3) sell out for the first time; 4) buy in for the second time; 5) sell out for the second time.
Define dp[i][j] (where j in {0,1,2,3,4}) as the max money you have on the ith day with status j.
One way to get to dp[i][0]: dp[i-1][0] when you have no action on the day before. The recurrence relation is dp[i][0] = dp[i-1][0].
Two ways to get to dp[i][1]: 1) dp[i-1][1] if you already buy a stock for the first time; 2) dp[i-1][0]-prices[i]if you buy a stock for the first time on the ith day. The recurrence relation is dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]).
Two ways to get to dp[i][2]: 1) dp[i-1][2] if you already sell a stock for the first time; 2) dp[i-1][1]+prices[i] if you sell a stock for the first time on the ith day. The recurrence relation is dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i]).
Two ways to get to dp[i][3]: 1) dp[i-1][3] if you already buy a stock for the second time; 2) dp[i-1][2]-prices[i] if you buy a stock for the second time on the ith day. The recurrence relation is dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]).
Two ways to get to dp[i][4]: 1) dp[i-1][4] if you already sell a stock for the second time; 2) dp[i-1][3]-prices[i] if you sell a stock for the second time on the ith day. The recurrence relation is dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i]).
The base case dp[0][0] = 0 if you have no action on the 0th day. dp[0][1]=-prices[0] if you but a stock on the 0th day.dp[0][2]=0 because you buy one and sell it on the 0th day. dp[0][3]=-prices[0] because you buy, sell, and but one stock on the 0th day. dp[0][4]=0 because you buy, sell, buy and sell a stock on the 0th day.
Time complexity is O(n). Space complexity O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length == 0: return 0
dp = [[0]*5 for _ in range(length)]
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i in range(1, length):
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
return dp[-1][4]
LeetCode 188
Best Time to Buy and Sell Stock IV (Hard) [link]
Key: You may complete at most k transactions.
Since you may complete at most k transactions, the size of j is 2*k+1. We can notice from LC 123 that if j is even, dp[0][j]=0 . If j is odd, dp[0][j]=-prices[0].
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
length = len(prices)
if length == 0: return 0
dp = [[0]*(2*k+1) for _ in range(length)]
for j in range(1, 2*k, 2):
dp[0][j] = -prices[0]
for i in range(1, length):
for j in range(0, 2*k-1, 2):
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i])
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])
return dp[-1][2*k]
Optimize space complexity to O(1).
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
length = len(prices)
if length == 0: return 0
dp = [0]*(2*k+1)
for j in range(1, 2*k, 2):
dp[j] = -prices[0]
for i in range(1, length):
for j in range(1, 2*k+1):
if j % 2:
dp[j] = max(dp[j], dp[j-1]-prices[i])
else:
dp[j] = max(dp[j], dp[j-1]+prices[i])
return dp[-1]
