Best Time to Buy and Sell Stock II

Introduction

Same price series as the single-transaction problem, one constraint relaxed: unlimited buy-and-sell pairs are allowed, as long as you never hold more than one share at a time. At first glance this is harder — the search space of “all possible non-overlapping transaction sets” is exponential. The surprise: this version is actually simpler than the single-transaction case. The optimal answer is one of the cleanest one-liners in interview DP.

The interesting interview content isn’t the greedy answer itself — it’s the correctness argument that justifies it, and the state-machine framing that ports cleanly to the harder cousin variants (cooldown, fee, limited transactions). This chapter walks all three: the one-line greedy, the proof that the one-liner is correct, and the DP framing that bridges to the rest of the family.

When a constraint is removed, sometimes the algorithm gets simpler — not more complex. The interview signal is recognizing the moment.

If you’re new to the buy/sell family, read the single-transaction chapter first, then come back. If you’ve coded LC 121, the greedy approach here will feel almost trivial — the value is in the state-machine framing, which is the gateway to the harder variants.

What the interviewer is actually testing

1. Recognizing the relaxation. Many candidates over-engineer LC 122 because they pattern-match it to LC 121 and write a more complex DP. The signal is noticing that unlimited trades is easier, not harder.
2. Articulating the correctness of the greedy. “Sum of positive deltas” sounds heuristic. Proving it equals the true optimum — by showing any larger trade decomposes into a sum of single-day trades — is the senior signal.
3. The state-machine framing. Two states (idle / holding), two transitions (buy / sell). This is the structure the rest of the family generalizes from.
4. Edge cases with no profitable trade. Strictly decreasing or constant inputs return 0 cleanly under the greedy formulation. Verifying that’s not a bug is part of the read.

Problem statement

Clarifying questions — and why each one matters

A mental framework — the relaxation makes it easier

LC 121 (single transaction) needed one number from the past — the running minimum — because you had to commit to a single buy day. LC 122 removes that constraint entirely. With unlimited trades, you don’t have to commit to anything: every profitable swing is independent of every other.

That changes the question. Instead of asking “what’s the best single buy/sell pair?”, ask “on each day, did the price go up?”. If yes, take the delta as a one-day trade. If no, skip. The total profit is the sum of all up-day deltas.

This isn’t a heuristic — it’s the optimum. Any longer trade [i, j] with $\text{prices}[j] > \text{prices}[i]$ telescopes:

Some of those daily deltas are positive, some negative. The greedy keeps only the positives — which is at least as much profit as the long trade gives, because the greedy can simply skip the down-days that the long trade is forced to absorb.

Discussion

#include <algorithm>
#include <vector>

namespace {
int solve(const std::vector<int>& P, int start) {
    int best = 0;
    const int n = static_cast<int>(P.size());
    for (int buyDay = start; buyDay < n - 1; ++buyDay) {
        for (int sellDay = buyDay + 1; sellDay < n; ++sellDay) {
            if (P[buyDay] < P[sellDay]) {
                const int profit = P[sellDay] - P[buyDay];
                best = std::max(best, profit + solve(P, sellDay + 1));
            }
        }
    }
    return best;
}
}  // namespace

int maxProfit(const std::vector<int>& prices) {
    return solve(prices, 0);
}

#include <vector>

int maxProfit(const std::vector<int>& prices) {
    int total = 0;
    for (std::size_t i = 1; i < prices.size(); ++i) {
        if (prices[i] > prices[i - 1]) {
            total += prices[i] - prices[i - 1];
        }
    }
    return total;
}

#include <algorithm>
#include <vector>

int maxProfit(const std::vector<int>& prices) {
    if (prices.empty()) return 0;
    int holding = -prices[0];  // best profit if currently holding a share
    int idle = 0;              // best profit if currently not holding
    for (std::size_t i = 1; i < prices.size(); ++i) {
        const int prevHolding = holding;
        holding = std::max(holding, idle - prices[i]);
        idle = std::max(idle, prevHolding + prices[i]);
    }
    return idle;
}

Approach comparison

Default answer: the greedy. State the telescoping correctness argument out loud when you close.

Follow-ups to anticipate

Pattern recognition — when constraint relaxation simplifies

This chapter teaches a pattern that’s worth naming explicitly: removing a constraint sometimes makes the algorithm simpler, not more complex. The intuition is that a tight constraint (LC 121: one trade) forces global commitment, which requires global state. A loose constraint (LC 122: any number of trades) decouples decisions across time, which lets a local greedy work.

Other problems with the same shape:

• Maximum Subarray vs. Maximum Sum Increasing Subsequence. The first is unconstrained on element selection (any contiguous range), and Kadane’s runs in $O(n)$. Adding the “increasing” constraint forces a more expensive DP.
• Minimum spanning tree (Kruskal’s). Without the spanning constraint, the answer is “no edges.” Adding the constraint forces a non-trivial algorithm. But within Kruskal’s, removing the no-cycle constraint would make every edge selectable — trivially.
• Coin change (with infinite supply) vs. 0/1 knapsack. Infinite supply allows a 1D DP; the 0/1 constraint forces 2D.

The reflex: when an interviewer relaxes a constraint and asks for the new answer, ask whether the relaxation decouples decisions across time or items. If yes, the answer might be a one-line greedy.

What to say out loud — the delivery script

Ten beats:

1. “Let me restate: same prices array as the single-transaction problem, but unlimited trades are allowed. Maximize total profit.”
2. Ask: “fee or cooldown? upper bound on n? profit or trade list?”
3. “Counterintuitively, this is easier than the single-transaction version. The reason: any long trade telescopes into a sum of single-day trades, and we can take every up-day independently.”
4. “So the greedy: walk left to right, sum every positive day-to-day delta. That’s the entire algorithm.”
5. Write the code — three lines.
6. “Correctness: any trade set is bounded above by the sum of positive deltas (telescoping argument). And the sum of positive deltas is achievable by a valid trade set (one trade per up-day). So they’re equal.”
7. Trace example 1: deltas are [-6, +4, -2, +3, -2]. Sum of positives: 4 + 3 = 7. Matches the expected output.
8. “Edge cases: strictly decreasing prices give 0 (no positive deltas); all-same prices give 0; single day gives 0. All handled by the loop body.”
9. “For the harder variants — fees, cooldowns, k-transaction limits — the greedy breaks. The state-machine DP is the framing that survives.”
10. “Complexity: $O(n)$ time, $O(1)$ space. I’d ship the greedy.”

Summary

The unlimited-transaction buy/sell problem is the rare case where relaxing a constraint simplifies the algorithm. Where the single-transaction version needs a running minimum and careful pair tracking, this version reduces to a one-line summation: sum every positive day-to-day delta.

The interview signal isn’t writing the three-line greedy. It’s two things: articulating the telescoping argument that proves the greedy is optimal, and recognizing the state-machine framing as the structural cousin of the harder family members. The greedy is what you ship; the state machine is what you say when the interviewer asks the next question in the family.