# LeetCode 122: Best Time to Buy and Sell Stock II

## Problem Restatement

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

We may buy and sell the stock multiple times, but we can hold at most one share at a time. That means we must sell before buying again.

We need to return the maximum profit possible.

For example:

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

The best strategy is:

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

Total profit:

```python
4 + 3 = 7
```

So the answer is:

```python
7
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of stock prices |
| Output | Maximum total profit |
| Transaction count | Unlimited |
| Holding rule | At most one share at a time |
| Same-day action | You may sell and buy again on the same day |
| No profit case | Return `0` |

The function shape is:

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

## Examples

For:

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

We collect the increasing parts:

```text
1 -> 5 gives 4
3 -> 6 gives 3
```

Total:

```python
7
```

For:

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

The price rises every day.

We can buy at `1` and sell at `5`, giving profit `4`.

Equivalently, we can take every daily increase:

```text
1 -> 2 gives 1
2 -> 3 gives 1
3 -> 4 gives 1
4 -> 5 gives 1
```

Total:

```python
4
```

For:

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

The price only decreases, so no profitable transaction exists.

The answer is:

```python
0
```

## First Thought: Find Every Buy-Sell Pair

Because multiple transactions are allowed, we might try every possible sequence of buys and sells.

But that becomes complicated. We would need to decide:

- when to buy,
- when to sell,
- when to skip,
- how to combine transactions.

A simpler observation gives the answer directly.

## Key Insight

Every positive daily price difference can be taken as profit.

If today's price is higher than yesterday's price, then this increase can contribute to the answer:

```python
prices[i] - prices[i - 1]
```

when it is positive.

For example:

```python
prices = [1, 5, 3, 6]
```

The profitable increases are:

```text
1 -> 5 gives 4
3 -> 6 gives 3
```

Total profit:

```python
7
```

This matches the best strategy:

```text
buy at 1, sell at 5
buy at 3, sell at 6
```

For a longer increasing run:

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

taking every small increase gives:

```python
(2 - 1) + (3 - 2) + (4 - 3) + (5 - 4) = 4
```

which is the same as:

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

So we do not need to locate exact valleys and peaks. Adding all positive adjacent differences is enough.

## Algorithm

Initialize:

```python
profit = 0
```

Then scan the array from day `1` to the end.

For each day `i`:

1. If `prices[i] > prices[i - 1]`, add the difference to `profit`.
2. Otherwise, skip it.

Return `profit`.

## Correctness

Any profitable transaction from a buy day `b` to a sell day `s` has profit:

```python
prices[s] - prices[b]
```

This difference can be decomposed into adjacent daily differences:

```text
(prices[b + 1] - prices[b])
+ (prices[b + 2] - prices[b + 1])
+ ...
+ (prices[s] - prices[s - 1])
```

If an adjacent difference is positive, taking it increases total profit. If it is zero or negative, taking it would not help.

Since we may perform multiple transactions and hold at most one share at a time, every positive adjacent increase can be realized by buying before the increase and selling after it.

Therefore, summing all positive adjacent increases gives a valid trading strategy.

No strategy can do better, because every buy-sell profit is made from the same adjacent differences, and negative differences can only reduce profit. The maximum possible total profit is exactly the sum of all positive adjacent differences.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the prices once |
| Space | `O(1)` | We store only the profit variable |

## Implementation

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

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

        return profit
```

## Code Explanation

Start with zero profit:

```python
profit = 0
```

Scan from the second day:

```python
for i in range(1, len(prices)):
```

If today's price is higher than yesterday's price:

```python
if prices[i] > prices[i - 1]:
```

then we add that increase:

```python
profit += prices[i] - prices[i - 1]
```

Finally:

```python
return profit
```

## Testing

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

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

        return profit

def run_tests():
    s = Solution()

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

    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, 2, 0, 1]) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[7,1,5,3,6,4]` | Standard multiple-transaction case |
| `[1,2,3,4,5]` | One long increasing run |
| `[7,6,4,3,1]` | No profit possible |
| Single price | Cannot sell after buying |
| Mixed rises and drops | Confirms only positive adjacent differences are counted |