[Leetcode]309. Best Time to Buy and Sell Stock with Cooldown

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.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Dynamic programming 1 – State Machine

Following the intuition using the state machine here in [Leetcode]121. Best Time to Buy and Sell Stock and [Leetcode]122. Best Time to Buy and Sell Stock II, let’s come up with the state transitions.

State transitions.

Here hold means holding 1 stock, cash means no stock in hands, and rest means no stocks in hands and ready to buy one. Hence, it’s easy to give the transition functions:

hold[i] = max(hold[i-1],rest[i-1]-prices[i])
cash[i] = hold[i-1]+prices[i]
rest[i] = max(rest[i-1],cash[i-1])
  • hold[i] means the largest profit we can make if we buy and hold the stock on day i.
  • cash[i] means the largest profit we can make if we sell the stock on day i.
  • rest[i] means the largest profit we can make if we rest on day i.
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        rest,hold,cash = [0]*len(prices),[0]*len(prices),[0]*len(prices)
        hold[0] = -prices[0]
        for i in range(1,len(prices)):
            hold[i] = max(rest[i-1]-prices[i],hold[i-1])
            cash[i] = hold[i-1]+prices[i]
            rest[i] = max(cash[i-1],rest[i-1])
        return max(cash[-1],rest[-1])

Typically, we could also reduce the space complexity from O(n) to O(1).

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        rest,hold,sold = 0,float('-inf'),0
        for price in prices:
            prev_sold = sold
            sold = hold+price
            hold = max(rest-price,hold)
            rest = max(prev_sold,rest)
        return max(sold,rest)

Dynamic programming 2

Another way of using dynamic programming, as explained in [Leetcode]188. Best Time to Buy and Sell Stock IV, is that we can define dp[i] as the largest profit we can make on day i. Therefore the transition function is:

dp[i] = max(dp[i-1],
        prices[i]-prices[j]+dp[j-2])

Note that the second item is using dp[j-2] because:

  • if we buy the stock on day j-1, then we can only use dp[j-2] because we need to buy it on day j.
  • if on day j-1 we take the rest, then we can take dp[j-1]. But since dp[j-1]==dp[j-2], the original transition function still holds.

Apparently we need a nested iteration to find the smallest prices[i]-prices[j]+dp[i-2]. However, with a small tweak of the function, instead of looking for max(prices[i]-prices[j]+dp[i-2]), we would look for min(prices[j]-dp[j-2]). In this way we would be able to use a single variable to record this minimum value.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        dp = [0] * (len(prices))
        dp[0] = 0
        dp[1] = max(0,prices[1]-prices[0])
        low = min(prices[:2])
        for i in range(2,len(prices)):
            low = min(low,prices[i]-dp[i-2])
            dp[i] = max(dp[i-1],prices[i]-low)
        return dp[-1]
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments