Best Time to Buy and Sell Stock with Cooldown

Problem Description

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 with the following restrictions: After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). You may not engage in multiple transactions simultaneously.

Key Insights

• You can buy and sell stock multiple times with a cooldown period after selling.
• Dynamic programming can be utilized to keep track of profits while adhering to the cooldown constraint.
• The problem can be broken down into states that represent different conditions: holding stock, not holding stock, and being in cooldown.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use dynamic programming to maintain three states:

1. hold: Maximum profit when holding a stock.
2. sold: Maximum profit when not holding a stock and just sold a stock.
3. cooldown: Maximum profit when in the cooldown state.

We iterate through the prices array and update these states based on the previous day's values. The key transitions are:

• If we hold a stock today, it can either be from holding it yesterday or buying it today.
• If we sell a stock today, it can only come from holding it yesterday.
• The cooldown state can only be reached from the sold state of the previous day.

At the end of the iteration, the maximum profit will be in the sold state.

Code Solutions