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:

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

The best strategy is:

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

Total profit:

4 + 3 = 7

So the answer is:

7

Input and Output

The function shape is:

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

Examples

For:

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

We collect the increasing parts:

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

Total:

7

For:

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:

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

Total:

4

For:

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

The price only decreases, so no profitable transaction exists.

The answer is:

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:

prices[i] - prices[i - 1]

when it is positive.

For example:

prices = [1, 5, 3, 6]

The profitable increases are:

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

Total profit:

7

This matches the best strategy:

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

For a longer increasing run:

[1, 2, 3, 4, 5]

taking every small increase gives:

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

which is the same as:

5 - 1 = 4

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

Algorithm

Initialize:

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:

prices[s] - prices[b]

This difference can be decomposed into adjacent daily differences:

(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

Implementation

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:

profit = 0

Scan from the second day:

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

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

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

then we add that increase:

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

Finally:

return profit

Testing

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: