Best Time To Buy And Sell Stock With — LeetCode 309, 714

Difficulty: Medium, Category: Dynamic Programming

309. Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock with Cooldown - LeetCode

Different from the basic Buy And Sell Stock problem, this problem has one more thing that needs to notice: after you sell a stock, you need a day to cool down, which means you cannot buy stock the next day.

We can consider it as three situations: hold, sell and cooldown.

• When you are at hold status, it’s either you hold on the previous day too or you just finished your cooldown after selling.
• After you buy a stock, you will enter the sell status.
• After sell, the only action you can do next is cooldown, and you could at the cooldown status when your previous action is cooldown or sell.

class Solution(object):
  def maxProfit(self, prices):
    hold, sell, cooldown = -float('inf'), 0, 0 
    
    for price in prices:
      prev_hold, prev_sell, prev_cooldown = hold, sell, cooldown

      # max profit of hold on Dayi
      # comes from hold on Dayi-1 or cooldown on Dayi-1 and buy on Dayi
      hold = max(prev_hold, prev_cooldown-price)

      # max profit of sell on Dayi
      # comes from hold on Dayi-1 and sell on Dayi
      sell = prev_hold + price

      # max profit of cooldown on Dayi
      # comes from cooldown on Dayi-1 or sell on Dayi-1 then cooldown on Dayi
      cooldown = max(prev_cooldown, prev_sell)

    return max(sell, cooldown)
      

• The reason for initiating hold as -float(‘int’) is because the first time we buy a stock, the profit will definitely be negative, when we need to use hold = max(prev_hold, prev_cooldown-price) to find the max profit of hold status, we need to make it set to a max negative value so that we can still get the first profit after buying the first stock.

714. Best Time to Buy and Sell Stock with Transaction Fee

Best Time to Buy and Sell Stock with Transaction Fee - LeetCode

• A transaction comes from one buy and one sell, and it will cost a transaction fee, in this example, we pay the transition fee when we sell the stock
• There are two statuses: buy and sell
• For buy status, it can be not doing any action with the previous buy price or do buy action and it will be prev-sell price minus current price
• For sell status, it can be not doing any action with the previous sell price or selling the stock with the previous buy price adding current prices, and don’t forget to minus the transition fee!

class Solution(object):
  def maxProfit(self, prices, fee):
    # record max profit of each day
    buy = [0]*len(prices)
    sell = [0]*len(prices)

    # for day0
    # buy the stock
    buy[0] = -prices[0]
    # can't sell when you have no stock, so sell max profit is 0
    # notice that you don't really need this line 
    # due to we create the dp list by value 0
    sell[0] = 0

    # from day1 to the last day
    for i in range(1, len(prices)):
      # not buy or buy one
      buy[i] = max(buy[i-1], sell[i-1]-prices[i])
      # not sell or sell one with transation fee
      sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee)

     return sell[-1]

Another method:

class Solution(object):
  def maxProfit(self, prices, fee):    
      buy = -prices[0]
      sell = 0
      for p in prices:
          prev_buy, prev_sell = buy, sell
          buy = max(prev_buy, prev_sell-p)
          sell = max(prev_sell, prev_buy+p-fee)

      return sell

• Only record the previous_buy and previous_sell and compare them with today’s buy action and sell action
• Buy action: not buying or buying the p price stock with prev_sell price
• Sell action: not selling or sell the p price stock with prev_buy price

REFERENCE
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108871/2-solutions-2-states-DP-solutions-clear-explanation!