# LeetCode 188: Best Time to Buy and Sell Stock IV

## Problem Restatement

We are given an integer `k` and an array `prices`.

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

We need to find the maximum profit possible with at most `k` transactions. One transaction means buying once and selling once. We cannot hold more than one stock at the same time, so we must sell before buying again. The official statement asks for the maximum profit with at most `k` transactions.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `k` and integer array `prices` |
| Output | Maximum profit |
| Transaction | One buy followed by one sell |
| Constraint | At most `k` transactions |
| Holding rule | Must sell current stock before buying again |

Example function shape:

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

## Examples

Example 1:

```python
k = 2
prices = [2, 4, 1]
```

Buy at price `2`, sell at price `4`.

Profit:

```text
4 - 2 = 2
```

There is no better second transaction.

Answer:

```python
2
```

Example 2:

```python
k = 2
prices = [3, 2, 6, 5, 0, 3]
```

One good plan is:

```text
Buy at 2, sell at 6 -> profit 4
Buy at 0, sell at 3 -> profit 3
```

Total profit:

```text
4 + 3 = 7
```

Answer:

```python
7
```

## First Thought: Try All Transactions

A brute force search could try every possible buy day and sell day for every transaction.

For one transaction, this already means many pairs.

For multiple transactions, we also need to decide where the next transaction starts.

This quickly becomes too slow because every choice creates more choices.

We need to reuse subproblem results.

## Key Insight

At any point, our state has two important parts:

| State | Meaning |
|---|---|
| Transaction count | How many completed sells we have used |
| Holding state | Whether we currently hold one stock |

For each transaction count `t`, we track two best values:

| Variable | Meaning |
|---|---|
| `buy[t]` | Best profit after buying or holding a stock using up to `t` transactions |
| `sell[t]` | Best profit after selling or holding no stock using up to `t` transactions |

A sell completes one transaction.

So when we sell for transaction `t`, we come from `buy[t]`.

When we buy for transaction `t`, we come from `sell[t - 1]`.

## Algorithm

Use dynamic programming with arrays of size `k + 1`.

Initialize:

```python
buy[t] = -infinity
sell[t] = 0
```

Then for every price:

1. For every transaction number `t` from `1` to `k`.
2. Update the best buy state:

```python
buy[t] = max(buy[t], sell[t - 1] - price)
```

3. Update the best sell state:

```python
sell[t] = max(sell[t], buy[t] + price)
```

At the end, `sell[k]` is the best profit with at most `k` transactions.

## Large k Optimization

If `k` is at least half the number of days, then the transaction limit stops mattering.

With `n` days, the maximum number of useful transactions is at most:

```text
n // 2
```

because each transaction needs at least one buy day and one later sell day.

So when:

```python
k >= len(prices) // 2
```

we can solve it like unlimited transactions: add every positive price increase.

```python
profit += max(0, prices[i] - prices[i - 1])
```

## Correctness

For each `t`, `buy[t]` stores the best profit possible after processing the current day while holding one stock and using at most `t` transactions.

There are two ways to reach this state.

We either already held a stock from an earlier day, so `buy[t]` stays the same, or we buy today after having completed at most `t - 1` transactions, giving:

```python
sell[t - 1] - price
```

So the update for `buy[t]` is correct.

For `sell[t]`, there are also two ways to reach the state.

We either already held no stock, so `sell[t]` stays the same, or we sell today from a holding state, completing transaction `t`, giving:

```python
buy[t] + price
```

So the update for `sell[t]` is correct.

The algorithm processes prices in chronological order, so every buy happens before its matching sell. Since buying uses `sell[t - 1]`, transactions cannot overlap.

At the end, the best valid result must hold no stock, because unsold stock does not contribute profit. Therefore, `sell[k]` is the maximum profit with at most `k` transactions.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(nk)` | For each day, we update `k` transaction states |
| Space | `O(k)` | We keep two arrays of length `k + 1` |

For the unlimited-transactions shortcut:

| Metric | Value |
|---|---|
| Time | `O(n)` |
| Space | `O(1)` |

## Implementation

```python
class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n = len(prices)

        if n < 2 or k == 0:
            return 0

        if k >= n // 2:
            profit = 0

            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    profit += prices[i] - prices[i - 1]

            return profit

        buy = [float("-inf")] * (k + 1)
        sell = [0] * (k + 1)

        for price in prices:
            for t in range(1, k + 1):
                buy[t] = max(buy[t], sell[t - 1] - price)
                sell[t] = max(sell[t], buy[t] + price)

        return sell[k]
```

## Code Explanation

This handles inputs where no profit can be made:

```python
if n < 2 or k == 0:
    return 0
```

This handles the unlimited-transactions case:

```python
if k >= n // 2:
```

When transactions are effectively unlimited, every upward price movement can be collected.

The DP arrays are:

```python
buy = [float("-inf")] * (k + 1)
sell = [0] * (k + 1)
```

`buy[t]` starts at negative infinity because holding a stock before buying is impossible.

`sell[t]` starts at `0` because doing nothing gives zero profit.

For every price, we update all transaction counts:

```python
for price in prices:
    for t in range(1, k + 1):
```

This line decides whether buying today improves the holding state:

```python
buy[t] = max(buy[t], sell[t - 1] - price)
```

This line decides whether selling today improves the non-holding state:

```python
sell[t] = max(sell[t], buy[t] + price)
```

Finally:

```python
return sell[k]
```

returns the best profit after at most `k` transactions while holding no stock.

## Testing

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

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `k = 2`, `[2, 4, 1]` | Basic one profitable transaction |
| `k = 2`, `[3, 2, 6, 5, 0, 3]` | Two separate profitable transactions |
| `k = 0` | No transactions allowed |
| Decreasing prices | No profit possible |
| Very large `k` | Uses unlimited-transactions shortcut |
| `k = 1` | Restricts answer to one transaction |