This series of Buy and Sell Stock I~VI on Leetcode is a great practice for Dynamic Programming – State Machine. Therefore I prepared blogs for each of them and hopefully it would help you to understand them better. You can find the relations of them at the bottom and feel free to leave any comments.
- [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]188. Best Time to Buy and Sell Stock IV
- [Leetcode]309. Best Time to Buy and Sell Stock with Cooldown
- [Leetcode]714. Best Time to Buy and Sell Stock with Transaction Fee
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.
From brute force O(n^2) to O(n)
The most straightforward approach would be: for each day
i, we would find the largest profit we could make if we buy the stock on day
j (j<i) with the lowest price and sell it on day
i. To find the lowest price that we can get, we could scan the stock
prices[0...i]. This would lead to O(n^2) time complexity, and if we could record the lowest price and update it during the iteration, we can get a O(n) solution.
class Solution: def maxProfit(self, prices: List[int]) -> int: total = 0 low = float('inf') for p in prices: low = min(low,p) total = max(total,p-low) return total
State machine – 1-D Dynamic programming
There are two states in this context:
hold holds stock in hand while
cash has no stock in hand. The way they can transit from one to the other is illustrated as below and one thing to notice is that, as we can only do 1 transaction, therefore there’s no path from
hold as we cannot rebuy the stock once we did.
class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 n = len(prices) hold,cash = *n,*n hold = -prices for i in range(1,n): hold[i] = max(hold[i-1],-prices[i]) cash[i] = max(cash[i-1],hold[i-1]+prices[i]) return cash[-1]
hold[i]means the largest profit we could make if we hold the stock on day
sold[i]means the largest profit we could make if we do not hold the stock on day
Moreover, we can further optimise it from O(n) space complexity to O(1). Noticing that
hold[i] is only affected by
cash[i] is only affected by
hold[i-1], instead of using arrays, we could use integers to record and update
hold if we update
class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 hold = -prices cash = 0 for price in prices[1:]: cash = max(cash,hold+price) hold = max(hold,-price) return cash
State machine – 2-D Dynamic programming
This 2D DP also follows the intuition of the state machine, yet it maintains the constraint of at most 1 transaction by using a 2-dimensional array. Actually this is a special case of the constraint that there are at most K transactions when
K=1, therefore more details about this approach is explained in 123. Best Time to Buy and Sell Stock III (Hard).
class Solution: def maxProfit(self, prices: List[int]) -> int: K = 1 if len(prices) < 2: return 0 dp =  * (K+1) low = [prices] * (K+1) for i in range(1,len(prices)): for k in range(1,K+1): low[k] = min(low[k],prices[i]-dp[k-1]) dp[k] = max(dp[k],prices[i]-low[k]) return dp[-1]