309. Best Time to Buy and Sell Stock with Cooldown

Problem Statement

link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example:

Input: prices = [1,2,3,0,2] Output: 3

Input: prices = [1] Output: 0

Solution Approach

Use dynamic programming to keep track of the maximum profit while considering the cooldown period.

Algorithm

1. Initialize three variables f0, f1, and f2 to represent the maximum profit on day i with the stock on hold, no stock in cooldown, and no stock not in cooldown, respectively.
2. Iterate through the prices array starting from the second day.
3. Update f0 to be the maximum of the previous f0 and f2 - prices[i], indicating whether to hold the stock or buy it on day i.
4. Update f1 to be the maximum of the previous f0 plus prices[i], indicating whether to sell the stock on day i.
5. Update f2 to be the maximum of the previous f1 and f2, representing whether to remain in a cooldown state or not.
6. After iterating through all days, return the maximum of f1 and f2 as the final maximum profit.

Implement

    # f[i] # f[i][0] on hold # f[i][1] no stock  in cooldown # f[i][2] no stock   not in cooldown  # f[i][0] = max f[i - 1][0] f[i - 1][2] - prices[i] # f[i][1] = max f[i - 1][0] + prices[i] # f[i][2] = max f[i - 1][1], f[i - 1][2] class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0 
        f0, f1, f2 = -prices[0], 0, 0
        for i in range(1, len(prices)):
            t0 = max(f0, f2 - prices[i])
            t1 = f0 + prices[i]
            f2 = max(f1, f2)
            f0, f1 = t0, t1
        return max(f1, f2)
      
 

    
    

Twitter  facebook  Email