Best Time to Buy and Sell Stock III

Introduction

The third entry in the buy/sell DP family. The relaxation that made the unlimited-transactions variant easier — every up-day is its own trade — has been pulled back. Now you can transact at most twice, which forces you to pick which two trades. The greedy that worked for unlimited transactions is no longer correct: there are inputs with five up-days where you have to drop three of them and keep only the most valuable two.

The chapter walks the standard arc — brute-force baseline, then two clean linear-time solutions. The two-pass approach with bestLeft and bestRight arrays is the most readable. The four-state DP that trims the space to $O(1)$ is the one to know cold; it’s the framing that survives all the way to LC 188 (at most $k$ transactions).

Adding a transaction cap forces a choice. The interview signal is the framing that turns the choice into a state machine.

If you haven’t read LC 121 and LC 122 yet, do that first — this chapter assumes the running-min and the unlimited-greedy are familiar territory. If you’ve coded the four-state DP before, jump to the correctness analysis under Approach 03; the subsidy trick is the part most candidates struggle to articulate.

What the interviewer is actually testing

1. Recognizing why the greedy breaks. A candidate who tries to apply LC 122’s “sum of positive deltas” with an upper bound on transactions has missed the constraint. Naming why it breaks — too many positive deltas, but only two transactions allowed — is the entry signal.
2. Comfort with multi-state DP. The two-pass approach is intuitive; the four-state collapse is the elegant answer. Demonstrating that you see them as the same algorithm with different state representations shows depth.
3. Articulating the subsidy trick. “After the first trade, I effectively have profit1 cash in hand, so the second buy at price p costs me only p − profit1.” That sentence is the senior signal. Most candidates code it correctly but fumble the explanation.
4. Knowing the family extension. This is the bridge between LC 121 / LC 122 (one or unlimited transactions) and LC 188 (at most k). Mentioning that the four-state DP generalizes to $2k$ states in the harder variant signals you’ve seen the family.

Problem statement

Clarifying questions — and why each one matters

A mental framework — the cap forces a choice

In LC 122 every up-day was independently profitable, so the greedy could capture them all. Adding at most two transactions changes the question from “should I take this up-day?” to “are these among the top two up-day clusters?”. Some up-days now have to be discarded — and which ones depends on the global structure of the price series, not on local information.

That global dependency is what forces the algorithm back into DP territory. Two approaches naturally fall out:

1. Split the problem in half. For every possible “split day” $i$, compute the best single trade in $[0, i]$ and the best single trade in $[i, n-1]$. Sum them and take the maximum. With prefix-/suffix-best arrays, this is $O(n)$ time and $O(n)$ space.

2. Roll the two trades together with a four-state recurrence. Track four running values that simultaneously represent “best position after 0, 0.5, 1, or 1.5 trades.” Each new day updates all four in turn. Same $O(n)$ time, but $O(1)$ space.

Both are correct. The two-pass is easier to derive from first principles; the four-state collapse is the senior code.

Discussion

#include <algorithm>
#include <climits>
#include <vector>

namespace {
int singleTradeBest(const std::vector<int>& prices, int lo, int hi) {
    if (lo >= hi) return 0;
    int best = 0;
    int minSeen = prices[lo];
    for (int i = lo; i <= hi; ++i) {
        minSeen = std::min(minSeen, prices[i]);
        best = std::max(best, prices[i] - minSeen);
    }
    return best;
}
}  // namespace

int maxProfit(const std::vector<int>& prices) {
    const int n = static_cast<int>(prices.size());
    if (n < 2) return 0;
    int best = 0;
    for (int split = 0; split < n; ++split) {
        const int p1 = singleTradeBest(prices, 0, split);
        const int p2 = singleTradeBest(prices, split, n - 1);
        best = std::max(best, p1 + p2);
    }
    return best;
}

#include <algorithm>
#include <vector>

int maxProfit(const std::vector<int>& prices) {
    const int n = static_cast<int>(prices.size());
    if (n < 2) return 0;

    std::vector<int> bestLeft(n, 0);
    int minL = prices[0];
    for (int i = 1; i < n; ++i) {
        minL = std::min(minL, prices[i]);
        bestLeft[i] = std::max(bestLeft[i - 1], prices[i] - minL);
    }

    std::vector<int> bestRight(n, 0);
    int maxR = prices[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        maxR = std::max(maxR, prices[i]);
        bestRight[i] = std::max(bestRight[i + 1], maxR - prices[i]);
    }

    int best = 0;
    for (int i = 0; i < n; ++i) {
        best = std::max(best, bestLeft[i] + bestRight[i]);
    }
    return best;
}

#include <algorithm>
#include <climits>
#include <vector>

int maxProfit(const std::vector<int>& prices) {
    if (prices.empty()) return 0;
    int buy1 = INT_MAX;   // cheapest price for the first buy
    int profit1 = 0;      // best profit after the first sale
    int buy2 = INT_MAX;   // cheapest effective second-buy cost (subsidized by profit1)
    int profit2 = 0;      // best total profit after the second sale
    for (const int p : prices) {
        buy1 = std::min(buy1, p);
        profit1 = std::max(profit1, p - buy1);
        buy2 = std::min(buy2, p - profit1);
        profit2 = std::max(profit2, p - buy2);
    }
    return profit2;
}

Approach comparison

Default answer: the four-state DP. State the subsidy trick out loud when you write buy2 = min(buy2, p - profit1) — that’s the line that makes the algorithm non-obvious.

Follow-ups to anticipate

Pattern recognition — collapsing 2D DP into running variables

This chapter teaches a specific structural move worth naming: when a 2D DP has dependencies that flow strictly forward in one dimension, the second dimension often collapses to a constant number of running variables.

LC 123’s natural DP is dp[i][t][holding] (day $i$, transactions completed $t$, currently holding stock or not). For $t \le 2$ and holding $\in \{0, 1\}$, that’s 4 logical states per day. The four-state DP is exactly that table compressed: each running variable corresponds to one $(t, \text{holding})$ combination, and the in-order updates implement the recurrence without ever materializing the table.

Other problems with the same shape:

• House Robber II (circular). A 2D state (current house, started-with-rob-or-skip) collapses to two running variables.
• Decode Ways. State (position, last-digit-context) collapses to two running variables.
• Distinct Subsequences. A 2D table where each row depends only on the previous row collapses to two rolling rows.
• Longest Common Subsequence with $O(\min(m, n))$ space. Same row-rolling collapse.

The reflex: when you have a 2D DP whose inner dimension has small bounded size, ask if the recurrence can be evaluated by chaining updates on running variables. When yes, the space drops from $O(n \cdot k)$ to $O(k)$ at no time cost.

What to say out loud — the delivery script

Ten beats:

1. “Let me restate: prices array, at most two non-overlapping buy/sell trades, maximize total profit.”
2. Ask: “at most 2 or exactly 2? trades can share a day? n bounds?”
3. “The greedy from LC 122 doesn’t work — too many up-days, only two transactions allowed. So I’m back in DP territory.”
4. “Brute force: try every split point, run LC 121 on each half. $O(n^2)$. Name and move on.”
5. “Two-pass linear: precompute bestLeft[i] (best trade in [0, i]) and bestRight[i] (best trade in [i, n-1]) with two sweeps. Answer is the max of bestLeft[i] + bestRight[i].”
6. “For constant space: four running variables — buy1, profit1, buy2, profit2. The trick is the second buy: buy2 = min(buy2, p - profit1) — the running first-trade profit subsidizes the second buy’s effective cost.”
7. Write the four-state code. Six lines.
8. “Correctness: profit1 is LC 121’s answer. buy2 = min over k of (prices[k] - profit1@k) is the cheapest effective second-buy. profit2 = max over i, k≤i of (prices[i] - prices[k] + profit1@k) is the optimum two-trade total.”
9. Trace example 1 ([3, 3, 5, 0, 0, 3, 1, 4]). Show that profit2 reaches 6 by day 7.
10. “Complexity: $O(n)$ time, $O(1)$ space. Generalizes to LC 188 (at most $k$ transactions) by tracking $2k$ running variables instead of 4.”

Summary

The two-transaction cap turns the buy/sell problem from a one-line greedy back into a real DP. Two clean linear-time solutions exist: the two-pass approach with bestLeft/bestRight arrays is the readable derivation; the four-state DP is the constant-space production answer. The teaching is the subsidy trick — using the running first-trade profit to discount the second buy — and the 2D-to-running-variable collapse that drops the space cost.

The four-state DP is also the bridge to the rest of the family. LC 188 generalizes it to $2k$ states; LC 309 adds a cooldown dimension; LC 714 adds a fee on the sell transition. All of them rotate this chapter’s structure rather than introducing a new one.