# Best Time to Buy and Sell Stock with Cooldown
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown)
Canonical: https://scaleengineer.com/dsa/problems/best-time-to-buy-and-sell-stock-with-cooldown
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Google](https://scaleengineer.com/companies/google), [Visa](https://scaleengineer.com/companies/visa), [Geico](https://scaleengineer.com/companies/geico)
---
## Problem
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 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`

# Approaches
## Brute-Force Recursion
This approach involves exploring every possible sequence of transactions (buy, sell, hold, rest) recursively. For each day, we make a decision based on whether we are currently holding a stock or not, and recursively calculate the profit for the subsequent days. This brute-force method checks all paths to find the optimal one.
**Time:** O(2^n), where n is the number of days. At each day, the function branches into two possibilities, leading to an exponential number of calls. · **Space:** O(n), where n is the number of days. This is due to the maximum depth of the recursion stack.
**Pros:** Conceptually simple and directly translates the problem statement into code.
**Cons:** Extremely inefficient due to redundant calculations of the same subproblems.; Leads to a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial input sizes.
### Explanation
The core idea is to define a function that represents the maximum profit we can get from a certain day onwards, given our current state (whether we hold a stock or not). This function will branch out, exploring all valid actions at each step.

For any given day `i`, if we don't have a stock, we can either buy one or rest. If we do have a stock, we can either sell it (and enter a cooldown period) or continue to hold it. The function recursively calls itself for each choice and returns the maximum profit found.

```java
class Solution {
    public int maxProfit(int[] prices) {
        return solve(0, true, prices);
    }

    // The 'canBuy' parameter indicates if we are in a state where buying is a possible action.
    private int solve(int day, boolean canBuy, int[] prices) {
        if (day >= prices.length) {
            return 0;
        }

        if (canBuy) {
            // We can either buy today or rest.
            int buyProfit = -prices[day] + solve(day + 1, false, prices);
            int restProfit = solve(day + 1, true, prices);
            return Math.max(buyProfit, restProfit);
        } else { // We are holding a stock and can either sell or hold.
            // We can either sell today (and cooldown) or hold.
            int sellProfit = prices[day] + solve(day + 2, true, prices);
            int holdProfit = solve(day + 1, false, prices);
            return Math.max(sellProfit, holdProfit);
        }
    }
}
```
### Algorithm
- Define a recursive function, say `solve(day, holdingStock)`, which calculates the maximum profit from a given `day` with a given `holdingStock` status.
- The `holdingStock` boolean indicates whether we currently own a share.
- **Base Case:** If `day` goes beyond the array length, no more transactions are possible, so return 0.
- **Recursive Step (If `holdingStock` is false):**
  - **Option 1 (Buy):** Buy the stock at `prices[day]`. The profit changes by `-prices[day]`, and we transition to a `holdingStock` state. The recursive call is `-prices[day] + solve(day + 1, true)`.
  - **Option 2 (Rest):** Do nothing. The profit doesn't change, and we stay in the `not holdingStock` state. The recursive call is `solve(day + 1, false)`.
  - Return the maximum of the two options.
- **Recursive Step (If `holdingStock` is true):**
  - **Option 1 (Sell):** Sell the stock at `prices[day]`. The profit changes by `+prices[day]`. Due to the cooldown, we must skip the next day. The recursive call is `prices[day] + solve(day + 2, false)`.
  - **Option 2 (Hold):** Do nothing. The profit doesn't change, and we stay in the `holdingStock` state. The recursive call is `solve(day + 1, true)`.
  - Return the maximum of the two options.
- The initial call to the function would be `solve(0, false)`.

## Recursion with Memoization
This approach, also known as top-down dynamic programming, optimizes the brute-force recursion by using memoization. We store the results of subproblems that have already been solved in a cache (e.g., a 2D array). When the same subproblem is encountered again, we retrieve the result from the cache instead of re-computing it, drastically reducing the number of calculations.
**Time:** O(n). Each state `(day, state)` is computed only once. There are `n * 2` such states. · **Space:** O(n). O(n) for the memoization table and O(n) for the recursion stack depth.
**Pros:** Significantly more efficient than brute-force, with linear time complexity.; Retains the logical structure of the recursive solution, which can be easier to reason about.
**Cons:** Uses O(n) space for the memoization table and recursion stack.; Can lead to a `StackOverflowError` for very deep recursion, although unlikely with the given constraints.
### Explanation
We enhance the recursive solution by adding a memoization table, `memo`, to store the results for each state `(day, state)`. The `state` can be represented by an integer: `1` for 'can buy' and `0` for 'can sell'.

Before making recursive calls to compute the profit for a state, we check our `memo` table. If a result already exists, we use it. Otherwise, we perform the computation and save the result in the table. This ensures that each unique subproblem is solved only once.

```java
import java.util.Arrays;

class Solution {
    public int maxProfit(int[] prices) {
        int[][] memo = new int[prices.length][2];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        // Start in a state where we can buy (state = 1)
        return solve(0, 1, prices, memo);
    }

    // state: 1 for 'can buy', 0 for 'can sell/holding'
    private int solve(int day, int state, int[] prices, int[][] memo) {
        if (day >= prices.length) {
            return 0;
        }
        if (memo[day][state] != -1) {
            return memo[day][state];
        }

        int profit;
        if (state == 1) { // Can buy
            int buyProfit = -prices[day] + solve(day + 1, 0, prices, memo);
            int restProfit = solve(day + 1, 1, prices, memo);
            profit = Math.max(buyProfit, restProfit);
        } else { // Can sell or hold
            int sellProfit = prices[day] + solve(day + 2, 1, prices, memo);
            int holdProfit = solve(day + 1, 0, prices, memo);
            profit = Math.max(sellProfit, holdProfit);
        }
        
        memo[day][state] = profit;
        return profit;
    }
}
```
### Algorithm
- Use the same recursive structure as the brute-force approach.
- Create a 2D memoization table, `memo[n][2]`, where `n` is the number of days and 2 represents the two states (can buy/can sell).
- Initialize the memoization table with a special value (e.g., -1) to indicate that a state has not been computed.
- In the recursive function `solve(day, state)`, first check if `memo[day][state]` has been computed. If so, return the stored value immediately.
- If not, compute the result using the recursive logic as before.
- Before returning the computed result, store it in `memo[day][state]` for future use.

## Dynamic Programming with State Machine (O(n) Space)
This approach uses bottom-up dynamic programming, modeling the problem as a finite state machine. We iterate through the days and, for each day, calculate the maximum profit achievable for three possible states: holding a stock (`buy`), having just sold a stock (`sell`), and being able to buy a stock (`rest`/`cooldown`).
**Time:** O(n), as we perform a single pass through the `prices` array. · **Space:** O(n), for the three DP arrays used to store the states for each day.
**Pros:** Efficient O(n) time complexity.; Avoids recursion overhead, making it slightly faster in practice than memoization.; The state transitions are very clear and easy to follow.
**Cons:** Uses O(n) space, which is not optimal for this problem.
### Explanation
We can solve this problem iteratively by building up the solution from day 0 to day `n-1`. We maintain three arrays to track the maximum profit at each day for each possible state.

- `buy[i]`: The maximum profit on day `i` if our last action was buying or holding.
- `sell[i]`: The maximum profit on day `i` if our last action was selling.
- `rest[i]`: The maximum profit on day `i` if our last action was resting or being in cooldown.

The value for each state on day `i` is calculated based on the values of the states on day `i-1`, representing the transitions in our state machine.

```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] rest = new int[n];

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

        for (int i = 1; i < n; i++) {
            buy[i] = Math.max(buy[i - 1], rest[i - 1] - prices[i]);
            sell[i] = buy[i - 1] + prices[i];
            rest[i] = Math.max(rest[i - 1], sell[i - 1]);
        }

        return Math.max(sell[n - 1], rest[n - 1]);
    }
}
```
### Algorithm
- Define three DP arrays of size `n`: `buy`, `sell`, and `rest`.
  - `buy[i]`: Max profit up to day `i`, ending in a 'bought' or 'holding' state.
  - `sell[i]`: Max profit up to day `i`, ending with a 'sell' on day `i`.
  - `rest[i]`: Max profit up to day `i`, ending in a 'rest' or 'cooldown' state.
- **Base Case (Day 0):**
  - `buy[0] = -prices[0]`
  - `sell[0] = 0`
  - `rest[0] = 0`
- **Transitions (Iterate from `i = 1` to `n-1`):**
  - `buy[i] = max(buy[i-1], rest[i-1] - prices[i])`: We either held from yesterday or bought today (after resting yesterday).
  - `sell[i] = buy[i-1] + prices[i]`: We must have been holding yesterday to sell today.
  - `rest[i] = max(rest[i-1], sell[i-1])`: We either rested from a previous rest state or are in cooldown after selling yesterday.
- **Final Result:** The maximum profit on the last day is `max(sell[n-1], rest[n-1])`, as we cannot end in a 'buy' state (it implies a net loss).

## Space-Optimized Dynamic Programming
This is the most optimized approach. It improves upon the O(n) space DP solution by observing that the calculation for any day `i` only depends on the state values from the previous day, `i-1`. Therefore, we don't need to store the entire history in arrays. We can use a few variables to keep track of the previous day's `buy`, `sell`, and `rest` profits, reducing the space complexity to a constant.
**Time:** O(n), as it requires a single pass through the input array. · **Space:** O(1), as we only use a constant number of variables to store the state profits, regardless of the input size.
**Pros:** Optimal solution with O(n) time and O(1) space complexity.; Highly efficient and practical for large inputs.
**Cons:** The logic for updating variables can be slightly tricky to get right, as the order of operations matters.
### Explanation
We can optimize the space complexity of the previous DP approach from O(n) to O(1). Since `buy[i]`, `sell[i]`, and `rest[i]` only depend on `buy[i-1]`, `sell[i-1]`, and `rest[i-1]`, we only need to maintain variables for the previous day's states, not the entire arrays.

We use three variables: `buy`, `sell`, and `rest` to hold the maximum profits for the current day being processed. Inside the loop, we calculate the new values for these states based on their values from the previous day. Care must be taken to use the previous day's values in all calculations within a single iteration.

```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int buy = -prices[0];
        int sell = 0;
        int rest = 0;

        for (int i = 1; i < prices.length; i++) {
            // Store the previous buy state before it's updated
            int prev_buy = buy;
            
            // Update buy state
            buy = Math.max(buy, rest - prices[i]);
            
            // Store previous sell state to update rest
            int prev_sell = sell;

            // Update sell state using the original buy value from previous day
            sell = prev_buy + prices[i];

            // Update rest state using the original sell value from previous day
            rest = Math.max(rest, prev_sell);
        }

        return Math.max(sell, rest);
    }
}
```
### Algorithm
- Initialize three variables to represent the states for day 0:
  - `buy = -prices[0]`
  - `sell = 0`
  - `rest = 0`
- Iterate from day `i = 1` to `n-1`.
- In each iteration, calculate the new state values based on the previous ones. It's crucial to use the values from the *previous* iteration, so we store one of them in a temporary variable before it gets updated.
  - `prev_buy = buy` (store the old `buy` state)
  - `buy = max(buy, rest - prices[i])`
  - `rest = max(rest, sell)` (update `rest` using the old `sell`)
  - `sell = prev_buy + prices[i]` (update `sell` using the old `buy`)
- After the loop, the maximum profit is `max(sell, rest)`.

# Solutions
### Java

```java
class Solution { public int maxProfit ( int [] prices ) { int f = 0 , f0 = 0 , f1 = - prices [ 0 ]; for ( int i = 1 ; i < prices . length ; ++ i ) { int g0 = Math . max ( f0 , f1 + prices [ i ]); f1 = Math . max ( f1 , f - prices [ i ]); f = f0 ; f0 = g0 ; } return f0 ; } }
```

### CPP

```cpp
class Solution {
public:
  int maxProfit(vector<int> &prices) {
    int f = 0, f0 = 0, f1 = -prices[0];
    for (int i = 1; i < prices.size(); ++i) {
      int g0 = max(f0, f1 + prices[i]);
      f1 = max(f1, f - prices[i]);
      f = f0;
      f0 = g0;
    }
    return f0;
  }
};

```

### Python

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int: f1, f2, f3 = - prices[0], 0, 0 for price in prices[1:]: pf1, pf2, pf3 = f1, f2, f3 f1 = max(pf1, pf3 - price) f2 = max(pf2, pf1 + price) f3 = max(pf3, pf2)  # cooldown return f2 ############ class Solution : def maxProfit ( self , prices : List [ int ]) -> int : f , f0 , f1 = 0 , 0 , - prices [ 0 ] for x in prices [ 1 :]: f , f0 , f1 = f0 , max ( f0 , f1 + x ), max ( f1 , f - x ) return f0 ############ class Solution ( object ): def maxProfit ( self , prices ): """ :type prices: List[int] :rtype: int """ if len ( prices ) < 2 : return 0 buy = [ 0 ] * len ( prices ) sell = [ 0 ] * len ( prices ) buy [ 0 ] = - prices [ 0 ] buy [ 1 ] = max ( - prices [ 1 ], buy [ 0 ]) sell [ 0 ] = 0 sell [ 1 ] = max ( prices [ 1 ] - prices [ 0 ], 0 ) for i in range ( 2 , len ( prices )): buy [ i ] = max ( sell [ i - 2 ] - prices [ i ], buy [ i - 1 ]) sell [ i ] = max ( prices [ i ] + buy [ i - 1 ], sell [ i - 1 ]) return max ( sell )

```