LC 309 & LC 714

Solution to LeetCode 309 Best Time to Buy and Sell Stock with Cooldown & LeetCode 714 Best Time to Buy and Sell Stock with Transaction Fee.

LeetCode 309

Best Time to Buy and Sell Stock with Cooldown (Medium) [link]

Key: You can complete as many transactions as you like, but you cannot hold multiple stocks at the same time, and after you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

1] Dynamic Programming

Define dp[i][j] as the max money you have on the ith day with status j.

There are 4 states: j in {0,1,2,3}.

1: j=0: You buy one stock today or already bought one before.

You may already have a stock dp[i][0] = dp[i - 1][0]. You may buy a stock right after a cooldown day dp[i - 1][3] - prices[i]. You may buy a stock when you already passed a cooldown day for some days dp[i - 1][1] - prices[i]. Therefore dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]).

2: j=1: You don’t have any stock because you sold it one day before, and you passed the cooldown day. You may sold the stock the day before yesterday, and yesterday is the cooldown day dp[i - 1][3]. You may already passed the cooldown day dp[i - 1][1]. Therefore dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]).

3: j=2: You don’t have any stock because you sold it today. You must have a stock and sold it today dp[i][2] = dp[i - 1][0] + prices[i].

4: j=3: cooldown day. You sold your stock yesterday. dp[i][3] = dp[i - 1][2].

In summary, the recurrence relation for 4 status is

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

To initialize the base cases:

dp[0][0] = -prices[0] because you have bought one stock. dp[0][1] = 0 because you bought and sold one stock on the first day. dp[0][2]=0, dp[0][3]=0 the same.

Time complexity = Space complexity = O(n).

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if length == 0: return 0
        dp = [[0]*4 for _ in range(length)]
        dp[0][0] = -prices[0]
        for i in range(1, length):
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])
            dp[i][2] = dp[i - 1][0] + prices[i]
            dp[i][3] = dp[i - 1][2]
        return max(dp[-1][1],dp[-1][2],dp[-1][3])

2] Alternative approach

Three states:

1 sold: max profit without holding stock (can’t buy, can’t sell)

dp[i][0] = dp[i-1][1] + prices[i]

2 holding: max profit with holding stock (can’t buy, can sell)

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

3 cooldown: max profit without holdings (can buy, can’t sell)

dp[i][2] = max(dp[i-1][2], dp[i-1][0])

Time complexity = Space complexity = O(n). Where n is the length of prices array.

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0
        sold = 0
        holding = -10**9
        cooldown = 0
        for j in prices:
            f0 = holding + j
            f1 = max(holding, cooldown - j)
            f2 = max(cooldown, sold)
            sold, holding, cooldown = f0, f1, f2
        return max(sold, cooldown)

LeetCode 714

Best Time to Buy and Sell Stock with Transaction Fee (Medium) [link]

Key: You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You must sell the stock before you buy again.

1] Dynamic Programming

Define dp[i][0] as the max money you have on the ith day if you have a stock, dp[i][1] as the max money you have on the ith day if you don’t have a stock.

dp[i][0] comes from 1) dp[i - 1][0] if you have the stock the day before; 2) dp[i - 1][1] - prices[i] if you buy one stock on the ith day. Therefore dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]).

dp[i][1] comes from 1) dp[i-1][1] if you don’t have any stock the day before; 2) dp[i-1][0]+prices[i]-fee if you sell a stock today. Therefore, dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee).

Time complexity O(n). Space complexity O(n).

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        length = len(prices)
        if length == 0: return 0
        dp = [[0]*2 for _ in range(length)]
        dp[0][0] = -prices[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]-fee)
        return max(dp[-1][0],dp[-1][1])

2] Alternative approach

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        ans = 0
        balance = -10**9
        for j in prices:
            ans = max(ans, balance + j - fee)
            balance = max(balance, ans - j)
        return ans