110. Best Time to Buy and Sell Stock II

Since you can trade freely, capture every price increase: any multi-day rise can be decomposed into consecutive one-day gains. So just add up every positive difference between consecutive days.

Idea

With unlimited transactions, the maximum profit is the sum of every upward move. A rise from day a to day c (through b) yields the same profit whether you hold the whole time or sell and rebuy: (c - a) = (b - a) + (c - b). So we never lose by grabbing each individual daily gain, and we never want to hold through a drop.

Algorithm

1. profit = 0.
2. For each consecutive pair, if prices[i] > prices[i-1], add prices[i] - prices[i-1] to profit.
3. Return profit.

Worked example: [7,1,5,3,6,4]

Profit = 4 + 3 = 7 (buy at 1 sell at 5; buy at 3 sell at 6).

Complexity

• Time: O(n) — one pass.
• Space: O(1).

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;
    }
}