0%

309. Best Time to Buy and Sell Stock with Cooldown

Posted on In

Ideas: This problem has two solutions. Both solutions use dynamic programming. The first solution maintains three status for each stock so that it runs faster with the time complexity O(n). The second solution uses classical dynamic programming equation which runs slower with the time complexity O(n^2).

Solution 1

There are three actions: buy, sell and do nothing. Relatively there are three status: hold a stock, cooldown and can buy a stock. We can conclude that: hold[i] = max( hold[i-1], canBuy[i-1] - prices[i] ). coolDown[i] =hold[i-1] + prices[i]. canBuy[i] = max(coolDown[i-1], canBuy[i-1]) .

1
2
3
4
5
6
7
8
def maxProfit1(prices) -> int:
    if len(prices) == 0:
        return 0
    prof = [-prices[0], 0, 0]
    for i in range(1, len(prices)):
        # prof[0] stands for hold status, prof[1] stands for coolDown status, prof[2] stands for canBuy status
        prof[0], prof[1], prof[2] = max(prof[0], prof[2]-prices[i]), prof[0] + prices[i], max(prof[1], prof[2])
    return max(prof)

Solution 2

Compute the maximum value from back to front. Using two traversals, the first loop locates each stock and the second loop calculates the maximum profit that the current stock can make on each subsequent sale. The core equation is profit[i] = max(profit[i], prices[j] - prices[i] + profit[j + 2]). And keep updating it profit[i] = max(profit[i], profit[i+1]).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxProfit(prices) -> int:
    n = len(prices)
    if n < 2:
        return 0
    profit = [0 for x in range(n)]
    i = n - 2
    while (i > -1):
        for j in range(i + 1, n):
            if prices[i] < prices[j]:
                if j >= n - 2:
                    profit[i] = max(profit[i], prices[j] - prices[i])
                else:
                    profit[i] = max(profit[i], prices[j] - prices[i] + profit[j + 2])
        i -= 1
        profit[i] = max(profit[i], profit[i + 1])
    return profit[0]