# LeetCode 123: Best Time to Buy and Sell Stock III

## Problem Restatement

We are given an array `prices`, where `prices[i]` is the stock price on day `i`.

We may complete at most two transactions.

One transaction means:

```text
buy once, then sell once
```

We cannot hold more than one share at a time, so we must sell before buying again.

We need to return the maximum possible profit.

For example:

```python
prices = [3, 3, 5, 0, 0, 3, 1, 4]
```

One best strategy is:

```text
buy at 0, sell at 3 -> profit 3
buy at 1, sell at 4 -> profit 3
```

Total profit:

```python
6
```

So the answer is:

```python
6
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of stock prices |
| Output | Maximum profit with at most two transactions |
| Transaction | One buy followed by one sell |
| Limit | At most two transactions |
| Holding rule | Cannot hold more than one share at a time |
| No profit case | Return `0` |

The function shape is:

```python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        ...
```

## Examples

For:

```python
prices = [3, 3, 5, 0, 0, 3, 1, 4]
```

A best plan is:

```text
buy at 0
sell at 3
buy at 1
sell at 4
```

The total profit is:

```python
3 + 3 = 6
```

So the answer is:

```python
6
```

For:

```python
prices = [1, 2, 3, 4, 5]
```

The best profit is made by buying at `1` and selling at `5`:

```python
5 - 1 = 4
```

Even though two transactions are allowed, we do not need to use both.

The answer is:

```python
4
```

For:

```python
prices = [7, 6, 4, 3, 1]
```

No profitable transaction exists.

The answer is:

```python
0
```

## First Thought: Split the Problem

With one transaction, we keep the lowest price seen so far.

With two transactions, the best answer can be seen as:

```text
best profit from first transaction
+
best profit from second transaction
```

But the second transaction must happen after the first transaction is complete.

A direct way is to try every split day:

```text
left side:  best one-transaction profit before or on this day
right side: best one-transaction profit after this day
```

Then take the best sum.

That works in `O(n)`, but we can compress the idea further.

## Key Insight

Track four states while scanning prices:

| State | Meaning |
|---|---|
| `buy1` | Best balance after first buy |
| `sell1` | Best profit after first sell |
| `buy2` | Best balance after second buy |
| `sell2` | Best profit after second sell |

A buy reduces our balance.

A sell increases our balance.

For each price, update:

```python
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
```

The final answer is:

```python
sell2
```

This also covers using only one transaction, because `sell2` can carry forward the best result without forcing a second useful trade.

## Algorithm

Initialize:

```python
buy1 = -prices[0]
sell1 = 0
buy2 = -prices[0]
sell2 = 0
```

Then scan each price.

For every `price`:

1. Update the best first buy.
2. Update the best first sell.
3. Update the best second buy after the first sell.
4. Update the best second sell.

Return `sell2`.

## Correctness

At every day, `buy1` stores the best possible balance after buying once. Since buying at price `p` gives balance `-p`, the best first buy is the largest value among all `-price` values seen so far.

`sell1` stores the best profit after completing one transaction. Selling today after the best first buy gives `buy1 + price`, so taking the maximum keeps the best one-transaction profit.

`buy2` stores the best possible balance after completing one transaction and then buying again. If we buy the second stock today, the balance becomes:

```python
sell1 - price
```

Taking the maximum keeps the best second-buy state.

`sell2` stores the best profit after completing at most two transactions. Selling the second stock today gives:

```python
buy2 + price
```

Taking the maximum keeps the best two-transaction profit.

These four states represent all valid progress stages of at most two transactions, in valid chronological order. Therefore, after all prices are processed, `sell2` is the maximum profit possible with at most two transactions.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the prices once |
| Space | `O(1)` | We store four state variables |

## Implementation

```python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        buy1 = -prices[0]
        sell1 = 0
        buy2 = -prices[0]
        sell2 = 0

        for price in prices:
            buy1 = max(buy1, -price)
            sell1 = max(sell1, buy1 + price)
            buy2 = max(buy2, sell1 - price)
            sell2 = max(sell2, buy2 + price)

        return sell2
```

## Code Explanation

The first buy starts as buying on day `0`:

```python
buy1 = -prices[0]
```

Before selling, profit is zero:

```python
sell1 = 0
```

The second buy can also start from the first price as a neutral initialization:

```python
buy2 = -prices[0]
```

The best profit after two sells starts at zero:

```python
sell2 = 0
```

For each price, update the first buy:

```python
buy1 = max(buy1, -price)
```

Then update the first sell:

```python
sell1 = max(sell1, buy1 + price)
```

Then update the second buy:

```python
buy2 = max(buy2, sell1 - price)
```

Then update the second sell:

```python
sell2 = max(sell2, buy2 + price)
```

Finally:

```python
return sell2
```

## Testing

```python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        buy1 = -prices[0]
        sell1 = 0
        buy2 = -prices[0]
        sell2 = 0

        for price in prices:
            buy1 = max(buy1, -price)
            sell1 = max(sell1, buy1 + price)
            buy2 = max(buy2, sell1 - price)
            sell2 = max(sell2, buy2 + price)

        return sell2

def run_tests():
    s = Solution()

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

    assert s.maxProfit([1, 2, 3, 4, 5]) == 4

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

    assert s.maxProfit([1]) == 0

    assert s.maxProfit([2, 1, 4, 5, 2, 9, 7]) == 11

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3,3,5,0,0,3,1,4]` | Standard two-transaction example |
| `[1,2,3,4,5]` | One transaction is enough |
| `[7,6,4,3,1]` | No profit possible |
| Single price | Cannot complete a transaction |
| Mixed prices | Confirms two separate profitable windows |