Buy Sell Stock with Cooldown (DP)

Maximize profit on a stock where you must rest one day after selling.

dynamic-programming state-machine stocks max-profit cooldown

You are given an integer array `prices` where `prices[i]` is the price of a given stock on the i-th day (0-indexed).

On each day, you may decide to buy or sell a stock, but you must follow these rules:
1. You may **not** engage in multiple transactions simultaneously (i.e., you must sell before buying again).
2. After you sell your stock, you **cannot buy stock on the next day** (i.e., there is a cooldown of one day).

Implement the function:

```python
def max_profit(prices):
    """
    Returns the maximum profit you can achieve, following the cooldown rule.
    """
```

**Return the maximum profit you can achieve.** If no profit is possible, return 0.

**Example 1:**
```python
max_profit([1,2,3,0,2])  # returns 3
```
Explanation: transactions = [buy, sell, cooldown, buy, sell].

**Example 2:**
```python
max_profit([1])  # returns 0
```

**Example 3:**
```python
max_profit([2,1])  # returns 0
```

Constraints

- `0 <= len(prices) <= 10^5`
- `0 <= prices[i] <= 10^5`
- Time complexity must be O(n) and space O(1) or O(n) is acceptable.
- The function should handle an empty list by returning 0.

Example

>>> max_profit([1,2,3,0,2])
3
>>> max_profit([1])
0
>>> max_profit([2,1])
0
>>> max_profit([3,3,5,0,0,3,1,4])
6

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a state-machine DP with three states: cooldown, holding, and sold (or rest, buy, sell).

Define variables like ``rest``, ``hold``, and ``sell``, updating them each day with the recurrence relations.

The cooldown state after a sale means you cannot buy on the next day, so you may need a variable for that.

Try to keep space O(1) by storing only the previous day's states.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.