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 i<sup>th</sup> 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 1:

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

Example 2:

Input: prices = [1]
Output: 0

Constraints:

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

Can you provide an efficient algorithm to solve this problem? What is the time and space complexity of your solution?

# Best Time to Buy and Sell Stock with Cooldown

This problem asks us to find the maximum profit that can be achieved by buying and selling a stock with a cooldown period of one day after each sale. We can perform multiple transactions, but we cannot buy on the day immediately following a sale.

## Naive Solution (Brute Force)

A brute-force approach would involve exploring all possible transaction sequences. This would involve recursion to try buying or not buying on each day, and selling or not selling if we own the stock. The time complexity of this approach would be exponential, making it impractical for larger input sizes.

## Optimal Solution (Dynamic Programming)

We can use dynamic programming to solve this problem efficiently. Let's define three states for each day:

*   `buy[i]` represents the maximum profit at day `i` if we buy stock on day `i`.
*   `sell[i]` represents the maximum profit at day `i` if we sell stock on day `i`.
*   `cooldown[i]` represents the maximum profit at day `i` if we do nothing (cooldown) on day `i`.

The state transitions are as follows:

*   `buy[i] = max(cooldown[i-1] - prices[i], buy[i-1])`
*   `sell[i] = buy[i-1] + prices[i]`
*   `cooldown[i] = max(cooldown[i-1], sell[i-1], buy[i-1])`

We can optimize space by using only three variables to store the previous states.

```python
def max_profit_with_cooldown(prices):
    if not prices:
        return 0

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

    for i in range(1, len(prices)):
        prev_buy = buy
        buy = max(cooldown - prices[i], buy)
        cooldown = max(cooldown, sell)
        sell = prev_buy + prices[i]

    return max(cooldown, sell)


# Example usage
prices = [1, 2, 3, 0, 2]
print(max_profit_with_cooldown(prices))  # Output: 3

prices = [1]
print(max_profit_with_cooldown(prices))  # Output: 0

Big(O) Run-time Analysis

The time complexity of the dynamic programming solution is O(n), where n is the number of days (length of the prices array). This is because we iterate through the prices array once to calculate the maximum profit for each day.

Big(O) Space Usage Analysis

The space complexity is O(1) because we only use a constant amount of extra space to store the buy, sell, and cooldown variables, regardless of the input size. We are optimizing the space usage by not storing every single day's calculation.

Edge Cases

1. Empty Input: If the prices array is empty, the function should return 0, as there are no opportunities to buy or sell.
2. Single Day: If there's only one day, no transaction can occur, so the function should return 0.
3. Decreasing Prices: If the prices are consistently decreasing, the function should return 0, as no profit can be made.
4. Large Input Size: The code should handle the maximum input size (5000) without performance issues, due to its O(n) time complexity.
5. Zero Prices: If all prices are zero, the function should return 0, as no profit can be made.