Best Time to Buy and Sell Stock II — Greedy Sum of Positive Deltas

The Problem

You are given an array prices where prices[i] is the stock price on day i. You can buy and sell as many times as you like, but you must sell before buying again (you can hold at most one share). Return the maximum profit.

This generalizes the single-transaction version. With unlimited transactions, the structure of the optimal strategy changes completely, and there is a very simple greedy proof.

Intuition

A recursive search tries, at every day, three actions: hold, buy if no position, or sell if holding. That is exponential. A DP on (day, holding) memoizes it down to O(n) time and O(1) space — correct, but heavy.

The cleaner observation: any profitable multi-day climb from day i to day j can be decomposed into the sum of daily deltas prices[k+1] - prices[k]. If every delta in the climb is added, the telescoping sum equals prices[j] - prices[i]. Negative deltas should be skipped — they correspond to days you would be holding through a dip, which you can avoid by selling at the local peak. So the answer is simply the sum of all positive daily deltas.

Explanation with Example

Take prices = [7, 1, 5, 3, 6, 4]. The deltas are -6, 4, -2, 3, -2. We keep the positive ones: 4 and 3. Total profit is 7.

day:    0  1  2  3  4  5
price:  7  1  5  3  6  4
delta:    -6 +4 -2 +3 -2
keep:        4     3
sum -> 7

The corresponding transactions are buy at 1, sell at 5 (profit 4), buy at 3, sell at 6 (profit 3). The greedy chose those peak-valley pairs implicitly.

Code

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        delta = prices[i] - prices[i - 1]
        if delta > 0:
            profit += delta
    return profit

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int delta = prices[i] - prices[i - 1];
            if (delta > 0) profit += delta;
        }
        return profit;
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (size_t i = 1; i < prices.size(); ++i) {
            int delta = prices[i] - prices[i - 1];
            if (delta > 0) profit += delta;
        }
        return profit;
    }
};

Edge Cases

An empty array or a single-day array yields 0 profit. A strictly decreasing array also yields 0 because every delta is negative. A strictly increasing array yields prices[-1] - prices[0] because every delta is positive and they telescope. Equal adjacent prices contribute zero — no harm. There are no overflow concerns for typical constraints.

If the problem variant adds a transaction fee, the greedy breaks down and you need DP. Same with a cooldown variant.

Complexity Analysis

Time is O(n): one pass over the array. Space is O(1): a single accumulator. This is optimal for any algorithm that must examine every price at least once.

The DP solution has the same complexity but with a larger constant factor and more state. The greedy is preferable purely because it is simpler to write and to defend.

How to Explain It in an Interview

Start with the decomposition argument: a profit from buying at day i and selling at day j equals the sum of daily deltas from i to j. Adding only positive deltas can only do as well or better than any contiguous range. Therefore the sum of positive deltas is the upper bound, and the corresponding transactions (peak-valley pairs) achieve it. Greedy is optimal.

Mention that this is different from the single-transaction version, where you track the minimum-so-far and the best profit ending at each day. With unlimited transactions the greedy makes the DP unnecessary.

If asked about transaction fees, immediately pivot to DP with two states, hold and cash. That signals you understand when greedy breaks.

Related Problems

• Best Time to Buy and Sell Stock — single transaction.
• Best Time to Buy and Sell Stock III — at most two transactions, DP.
• Best Time to Buy and Sell Stock IV — at most k transactions.
• Buy and Sell with Cooldown.
• Buy and Sell with Transaction Fee.