Best Time to Buy and Sell Stock with Cooldown medium

Problem Statement

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

Find the maximum profit you can achieve. 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 simultaneously (i.e., you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on the next day. (i.e., cooldown 1 day)

Example 1:

Input: prices = [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1] Output: 0

Steps and Explanation

This problem can be solved using dynamic programming. We'll maintain three arrays:

• buy[i]: The maximum profit if we buy the stock on day i.
• sell[i]: The maximum profit if we sell the stock on day i.
• rest[i]: The maximum profit if we are in a cooldown state on day i (meaning we neither bought nor sold).

The base cases are:

• buy[0] = -prices[0] (buying on day 0)
• sell[0] = 0 (can't sell on day 0 without buying first)
• rest[0] = 0 (no profit on day 0)

The recurrence relations are:

• buy[i] = max(buy[i-1], rest[i-1] - prices[i]): Either we don't buy on day i (same as yesterday's buy profit), or we buy on day i (yesterday's rest profit minus today's price).
• sell[i] = max(sell[i-1], buy[i-1] + prices[i]): Either we don't sell on day i (same as yesterday's sell profit), or we sell on day i (yesterday's buy profit plus today's price).
• rest[i] = max(rest[i-1], sell[i-1]): Either we remain in cooldown (same as yesterday's rest profit), or we end the cooldown after a sale (yesterday's sell profit).

Finally, the maximum profit will be max(sell[n-1], rest[n-1]) where n is the length of prices.

Code

def maxProfit(prices):
    n = len(prices)
    if n <= 1:
        return 0

    buy = [0] * n
    sell = [0] * n
    rest = [0] * n

    buy[0] = -prices[0]
    sell[0] = 0
    rest[0] = 0

    for i in range(1, n):
        buy[i] = max(buy[i-1], rest[i-1] - prices[i])
        sell[i] = max(sell[i-1], buy[i-1] + prices[i])
        rest[i] = max(rest[i-1], sell[i-1])

    return max(sell[n-1], rest[n-1])

Complexity

• Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once.
• Space Complexity: O(n), due to the buy, sell, and rest arrays. This can be optimized to O(1) by only storing the values for the current and previous day, instead of the entire history. However, the provided code is more readable.