# LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee

## Problem Restatement

We are given an array `prices`.

```python
prices[i]
```

is the price of a stock on day `i`.

We are also given an integer `fee`.

We may complete as many transactions as we want, but we cannot hold more than one share at the same time. That means we must sell the current stock before buying again.

Each completed transaction pays the transaction fee once.

Return the maximum profit we can achieve.

The official problem states that the fee is paid once for each buy-sell transaction, and multiple simultaneous transactions are not allowed.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `prices`, a list of stock prices |
| Input | `fee`, the transaction fee |
| Output | Maximum possible profit |
| Allowed transactions | As many as we want |
| Restriction | Must sell before buying again |
| Fee rule | Fee is paid once per completed transaction |

The function shape is:

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

## Examples

Example 1:

```python
prices = [1, 3, 2, 8, 4, 9]
fee = 2
```

One optimal strategy is:

| Action | Price | Profit Change |
|---|---:|---:|
| Buy | `1` | `-1` |
| Sell | `8` | `+8 - 2` |
| Buy | `4` | `-4` |
| Sell | `9` | `+9 - 2` |

Total profit:

```python
(8 - 1 - 2) + (9 - 4 - 2) = 8
```

Output:

```python
8
```

Example 2:

```python
prices = [1, 3, 7, 5, 10, 3]
fee = 3
```

Output:

```python
6
```

## First Thought: Try Every Buy and Sell Choice

A brute force approach is to consider every possible action on every day.

On each day, we can:

1. Do nothing.
2. Buy, if we are not holding a stock.
3. Sell, if we are holding a stock.

This naturally leads to recursion.

The problem is that many states repeat. For example, reaching day `i` while holding a stock can happen through many different earlier action sequences.

Without memoization, this becomes exponential.

## Key Insight

At the end of each day, we only need two states.

| State | Meaning |
|---|---|
| `cash` | Maximum profit after this day while holding no stock |
| `hold` | Maximum profit after this day while holding one stock |

Every valid strategy must be in exactly one of these states.

For each price, we update these two values.

If we end the day with no stock, either:

1. We already had no stock.
2. We sell today.

If we end the day holding stock, either:

1. We were already holding.
2. We buy today.

We can charge the fee when selling.

## Recurrence

Let `price` be today's price.

To update `cash`:

```python
cash = max(cash, hold + price - fee)
```

This means:

| Choice | Profit |
|---|---|
| Do not sell | `cash` |
| Sell today | `hold + price - fee` |

To update `hold`:

```python
hold = max(hold, old_cash - price)
```

This means:

| Choice | Profit |
|---|---|
| Do not buy | `hold` |
| Buy today | `old_cash - price` |

We use `old_cash` because buying should use the no-stock profit from before today's update.

## Algorithm

1. Set `cash = 0`.
2. Set `hold = -prices[0]`.
3. For each later price:
   - Save `old_cash = cash`.
   - Update `cash` by either keeping cash or selling.
   - Update `hold` by either keeping hold or buying.
4. Return `cash`.

The answer is `cash` because the best final result should not end with an unsold stock. Holding a stock means we paid for it but did not realize its value as profit.

## Correctness

We prove that after each day, `cash` and `hold` represent the best possible profits for their states.

At the start, before any sale, the best no-stock profit is `0`. If we buy on the first day, the best holding profit is `-prices[0]`. So the initialization is correct.

Assume the values are correct before processing a day with price `price`.

To end the day with no stock, there are only two possibilities. Either we already had no stock and do nothing, giving profit `cash`, or we sell the stock we were holding, giving profit `hold + price - fee`. Taking the maximum gives the best no-stock profit.

To end the day holding stock, there are also only two possibilities. Either we were already holding and do nothing, giving profit `hold`, or we buy today using a previous no-stock state, giving profit `old_cash - price`. Taking the maximum gives the best holding profit.

These transitions cover all legal actions and exclude illegal simultaneous transactions because buying is only allowed from the no-stock state and selling is only allowed from the holding state.

Therefore the states remain correct after every day. At the end, the maximum realized profit is `cash`, so returning it is correct.

## Complexity

Let `n` be the number of days.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process each price once |
| Space | `O(1)` | We keep only two DP states |

## Implementation

```python
class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        cash = 0
        hold = -prices[0]

        for price in prices[1:]:
            old_cash = cash

            cash = max(cash, hold + price - fee)
            hold = max(hold, old_cash - price)

        return cash
```

## Code Explanation

The no-stock state starts at zero profit:

```python
cash = 0
```

The holding state starts as if we bought on the first day:

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

Before updating `cash`, save its old value:

```python
old_cash = cash
```

Then decide whether to sell today:

```python
cash = max(cash, hold + price - fee)
```

Then decide whether to buy today:

```python
hold = max(hold, old_cash - price)
```

Finally, return the best profit while holding no stock:

```python
return cash
```

## Alternative Fee Placement

We can also charge the fee when buying instead of selling.

```python
class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        cash = 0
        hold = -prices[0] - fee

        for price in prices[1:]:
            old_cash = cash

            cash = max(cash, hold + price)
            hold = max(hold, old_cash - price - fee)

        return cash
```

Both versions are correct as long as the fee is charged exactly once per completed transaction.

## Example Walkthrough

Use:

```python
prices = [1, 3, 2, 8, 4, 9]
fee = 2
```

Initialize:

```python
cash = 0
hold = -1
```

Process price `3`:

```python
cash = max(0, -1 + 3 - 2) = 0
hold = max(-1, 0 - 3) = -1
```

Process price `2`:

```python
cash = max(0, -1 + 2 - 2) = 0
hold = max(-1, 0 - 2) = -1
```

Process price `8`:

```python
cash = max(0, -1 + 8 - 2) = 5
hold = max(-1, 0 - 8) = -1
```

Process price `4`:

```python
cash = max(5, -1 + 4 - 2) = 5
hold = max(-1, 5 - 4) = 1
```

The `hold = 1` state means we have already made profit `5`, then bought again at price `4`, leaving net profit `1`.

Process price `9`:

```python
cash = max(5, 1 + 9 - 2) = 8
hold = max(1, 5 - 9) = 1
```

Final answer:

```python
8
```

## Testing

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

    assert s.maxProfit([1, 3, 2, 8, 4, 9], 2) == 8
    assert s.maxProfit([1, 3, 7, 5, 10, 3], 3) == 6
    assert s.maxProfit([1], 0) == 0
    assert s.maxProfit([5, 4, 3, 2, 1], 1) == 0
    assert s.maxProfit([1, 2, 3, 4, 5], 0) == 4
    assert s.maxProfit([1, 4, 6, 2, 8, 3, 10, 14], 3) == 13

    print("all tests passed")

test_max_profit_with_fee()
```

Test coverage:

| Test | Why |
|---|---|
| Standard example | Confirms multiple transactions with fee |
| Second example | Confirms fee can merge nearby trades |
| Single day | Confirms no possible sale |
| Decreasing prices | Confirms no losing trade is forced |
| Zero fee | Reduces to unlimited stock trading |
| Multiple profitable intervals | Confirms repeated state transitions |