# LeetCode 309: Best Time to Buy and Sell Stock with Cooldown

## Problem Restatement

We are given an integer array `prices`.

`prices[i]` is the price of a stock on day `i`.

We may complete as many transactions as we want, but with two restrictions:

1. We cannot hold more than one stock at the same time.
2. After selling a stock, we cannot buy on the next day. That next day is a cooldown day.

Return the maximum profit we can make.

The official constraints are `1 <= prices.length <= 5000` and `0 <= prices[i] <= 1000`. The problem is tagged as Array and Dynamic Programming.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `prices` |
| Output | Maximum possible profit |
| Buy rule | Can buy only when not holding stock |
| Sell rule | Can sell only when holding stock |
| Cooldown rule | After selling, cannot buy on the next day |

Function shape:

```python
def maxProfit(prices: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
prices = [1, 2, 3, 0, 2]
```

Output:

```python
3
```

One optimal sequence is:

```text
buy, sell, cooldown, buy, sell
```

This means:

| Day | Price | Action | Profit Change |
|---:|---:|---|---:|
| 0 | `1` | Buy | `-1` |
| 1 | `2` | Sell | `+2` |
| 2 | `3` | Cooldown | `0` |
| 3 | `0` | Buy | `0` |
| 4 | `2` | Sell | `+2` |

Total profit:

```python
-1 + 2 + 0 + 0 + 2 = 3
```

Example 2:

```python
prices = [1]
```

Output:

```python
0
```

There is only one day, so no sell can happen after a buy.

## First Thought: Try Every Choice

On each day, we may have several choices:

| State | Possible Actions |
|---|---|
| Not holding stock | Buy or skip |
| Holding stock | Sell or keep holding |
| Just sold yesterday | Cooldown, so cannot buy today |

A recursive solution can try all valid choices.

But without memoization, the same subproblems repeat many times.

For example, many different action paths may lead to:

```text
day 4, not holding stock
```

So plain recursion becomes exponential.

We need dynamic programming.

## Key Insight

The decision on each day depends only on our current state.

We do not need the full transaction history.

We only need to know the best profit after each day in these states:

| State | Meaning |
|---|---|
| `hold` | Maximum profit after today while holding one stock |
| `sold` | Maximum profit after today if we sold today |
| `rest` | Maximum profit after today while not holding stock and not selling today |

These three states encode the cooldown rule.

If we sell today, tomorrow we cannot buy. That state is represented by `sold`.

If we are in `rest`, we are free to buy.

## State Transitions

For each price `p`, compute the next states.

### Holding stock

At the end of today, we hold stock in one of two ways:

1. We already held stock yesterday.
2. We were resting yesterday and buy today.

```python
new_hold = max(hold, rest - p)
```

We cannot buy from `sold`, because that would mean buying immediately after selling yesterday.

### Sold today

At the end of today, we are in `sold` only if we held stock yesterday and sell today.

```python
new_sold = hold + p
```

### Resting

At the end of today, we are resting if:

1. We were already resting yesterday.
2. We sold yesterday and today is the cooldown day.

```python
new_rest = max(rest, sold)
```

These three transitions enforce all rules.

## Algorithm

Initialize:

```python
hold = -infinity
sold = -infinity
rest = 0
```

Before any day:

| State | Value | Reason |
|---|---:|---|
| `hold` | `-infinity` | Cannot be holding before buying |
| `sold` | `-infinity` | Cannot have sold before any day |
| `rest` | `0` | Doing nothing gives zero profit |

For each price:

1. Compute `new_hold`.
2. Compute `new_sold`.
3. Compute `new_rest`.
4. Replace old states with new states.

At the end, return:

```python
max(sold, rest)
```

We do not return `hold`, because holding a stock at the end means we spent money on an unsold stock. Selling it would be required to realize profit.

## Correctness

For each day, the three DP states represent the best possible profit among all valid action sequences ending in that state.

The initialization is correct because before trading starts, the only possible state is resting with profit `0`.

Assume the states are correct after yesterday.

For today:

`new_hold` is correct because the only ways to end today holding stock are to keep holding from yesterday, or buy today from a resting state. Buying from yesterday's `sold` state is forbidden by the cooldown rule.

`new_sold` is correct because the only way to sell today is to have held stock yesterday.

`new_rest` is correct because we can rest after already resting, or spend today as the cooldown day after selling yesterday.

These cases cover every valid action and exclude every invalid action. Therefore, the states remain correct after every day.

At the end, the best realized profit must be in `sold` or `rest`, because holding a stock means the last buy has not been closed by a sell. Thus `max(sold, rest)` is the maximum possible profit.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We process each price once |
| Space | `O(1)` | We store only three states |

## Implementation

```python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        hold = float("-inf")
        sold = float("-inf")
        rest = 0

        for price in prices:
            new_hold = max(hold, rest - price)
            new_sold = hold + price
            new_rest = max(rest, sold)

            hold = new_hold
            sold = new_sold
            rest = new_rest

        return max(sold, rest)
```

## Code Explanation

We start with three states:

```python
hold = float("-inf")
sold = float("-inf")
rest = 0
```

`rest = 0` means we have done nothing and made no profit.

`hold` and `sold` are impossible before processing any day, so they start as negative infinity.

For each price:

```python
for price in prices:
```

Compute the next holding state:

```python
new_hold = max(hold, rest - price)
```

This means either keep holding, or buy today from a free resting state.

Compute the next sold state:

```python
new_sold = hold + price
```

This means sell the stock we held before today.

Compute the next rest state:

```python
new_rest = max(rest, sold)
```

This means either continue resting, or enter cooldown after selling yesterday.

Then update all states together:

```python
hold = new_hold
sold = new_sold
rest = new_rest
```

Updating together matters. Each new state must be based on yesterday's states, not partially updated values from today.

Finally:

```python
return max(sold, rest)
```

This returns the best profit when we finish without holding stock.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxProfit([1, 2, 3, 0, 2]) == 3
    assert s.maxProfit([1]) == 0
    assert s.maxProfit([1, 2]) == 1
    assert s.maxProfit([2, 1]) == 0
    assert s.maxProfit([1, 2, 3]) == 2
    assert s.maxProfit([6, 1, 6, 4, 3, 0, 2]) == 7
    assert s.maxProfit([0, 0, 0]) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3, 0, 2]` | Standard cooldown example |
| `[1]` | No complete transaction possible |
| `[1, 2]` | One simple profitable trade |
| `[2, 1]` | No profitable trade |
| `[1, 2, 3]` | Best is buy once and sell once |
| `[6, 1, 6, 4, 3, 0, 2]` | Cooldown affects later buying |
| `[0, 0, 0]` | Zero-price edge case |