[Leetcode]121. Best Time to Buy and Sell Stock

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.

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 cash to hold as we cannot rebuy the stock once we did.

State transitions.
class Solution:
    def maxProfit(self, prices: List[int]) -> int:        
        if not prices:
            return 0
        n = len(prices)
        hold,cash = [0]*n,[0]*n
        hold[0] = -prices[0]
        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 i.
  • sold[i] means the largest profit we could make if we do not hold the stock on day i.
State transitions.

Moreover, we can further optimise it from O(n) space complexity to O(1). Noticing that hold[i] is only affected by hold[i-1] and cash[i] is only affected by cash[i-1] and hold[i-1], instead of using arrays, we could use integers to record and update cash and hold if we update cash first.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:        
        if not prices:
            return 0
        hold = -prices[0]
        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 = [0] * (K+1)
        low = [prices[0]] * (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]

Relations

Relations among this series problems of ‘buy and sell stock’.
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments