Best Time to Buy and Sell Stock II

This problem is a clean greedy exercise: you can make as many transactions as you want, but you can hold only one stock at a time. The goal is to collect every profitable upward move.

Problem

Given an array prices, where prices[i] is the stock price on day i, return the maximum profit.

Rules:

• You may buy and sell multiple times.
• You must sell before buying again.
• You may skip any day.

First Attempt

My first version compressed each rising segment into one transaction:

public int maxProfit(int[] prices) {
    var i = 0;
    var profit = 0;
    var n = prices.length;

    while (i < n) {
        var min = prices[i];
        var j = i + 1;

        while (j < n - 1 && prices[j] > min && prices[j + 1] > prices[j]) {
            j++;
        }

        if (j < n && prices[j] > min) {
            profit += prices[j] - min;
        }

        i = j;
    }

    return profit;
}

The instinct is right: find a valley, walk to the peak, take the profit, and continue.

For example:

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

Useful rising segments:

1 -> 5 = 4
3 -> 6 = 3
total = 7

What Changed

The rising-segment idea can be simplified.

Instead of explicitly finding every valley and peak, just add every positive day-to-day price difference:

1 -> 5 contributes 4
3 -> 6 contributes 3

For a longer rise:

1 -> 2 -> 3 -> 5

Buying at 1 and selling at 5 gives:

5 - 1 = 4

Adding daily gains gives the same result:

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

That is the greedy trick. Every upward edge is profit we are allowed to capture.

Final Version

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }

        return profit;
    }
}

Why This Works

Because unlimited transactions are allowed, every positive slope can be treated as a small buy-sell opportunity.

If prices keep rising for several days, summing the daily gains equals buying at the first low and selling at the final high.

If prices fall or stay flat, there is no profit to collect.

Complexity

Edge Cases

[7, 6, 4, 3, 1] -> 0
[1, 2, 3, 4, 5] -> 4
[7, 1, 5, 3, 6, 4] -> 7
[1] -> 0
[] -> 0

Takeaways

• When unlimited transactions are allowed, collect every positive slope.
• A peak-valley scan is correct, but summing positive differences is simpler.
• The constraint "must sell before buying again" is still respected because each positive edge represents a valid local transaction.
• This is a greedy pattern: take every local gain because it never blocks a better future gain.