Best Time to Buy and Sell Stock III

Hard20–25 min

Topics

Dynamic Programming

Companies

GoogleAmazonBloomberg

Given daily stock `prices`, complete at most two buy-sell transactions — never holding more than one share at a time, and always selling the current share before buying the next one. Maximize total profit; skipping trading entirely (profit 0) is always allowed. The single-transaction version tracks one running number: the best profit reachable by day `i`. Adding a second transaction means that number now has to fork into four, one per stage of the two-transaction journey — holding after buy one, settled after sell one, holding again after buy two, settled after sell two. Each stage can only be reached by first passing through the stage before it, so sweeping through the prices once and refreshing all four numbers in that fixed order — buy one, sell one, buy two, sell two — keeps every stage built only on information that's already correct by the time it's used.

Test Case 1:

Input:prices = [3,3,5,0,0,3,1,4]

Output:6

Explanation:Buy at 0 (day 3), sell at 3 (day 5) for 3, then buy at 1 (day 6), sell at 4 (day 7) for another 3 — two separate transactions totaling 6.

Test Case 2:

Input:prices = [1,2,3,4,5]

Output:4

Explanation:Prices only ever climb, so a single buy-at-1, sell-at-5 run already captures every bit of profit — the second transaction has nothing left to add.

Test Case 3:

Input:prices = [7,6,4,3,1]

Output:0

Explanation:Prices only ever fall, so no buy is ever followed by a higher sell — skip trading entirely and take 0.

Constraints

◆1 ≤ prices.length ≤ 10
◆0 ≤ prices[i] ≤ 1000
◆at most two buy-sell transactions are allowed; you must sell before buying again

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

At every day there are exactly two choices depending on whether a share is currently held: buy or hold if not holding, sell or hold if holding. Trying both choices at every day and recursing covers every possible pair of transactions, but nothing is remembered between calls — the same (day, holding, transactions-remaining) situation gets explored over and over on different branches, so the work roughly doubles with every extra day.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] prices;

    public int maxProfit(int[] prices) {
        this.prices = prices;
        return solve(0, false, 2);
    }

    private int solve(int day, boolean holding, int txnsLeft) {
        if (day == prices.length || txnsLeft == 0) return 0;
        int doNothing = solve(day + 1, holding, txnsLeft);
        int act;
        if (holding) {
            act = prices[day] + solve(day + 1, false, txnsLeft - 1);
        } else {
            act = -prices[day] + solve(day + 1, true, txnsLeft);
        }
        return Math.max(doNothing, act);
    }
}

Optimal — Two-Transaction State Tracking

Optimal

Rather than branching on every day's decision, keep four running numbers that summarize the best result reachable so far under each of four situations: holding after the first buy, cash after the first sell, holding after the second buy (only reachable once a first sell already happened), and cash after the second sell. Each new day's price can only improve these four numbers, never make them worse, so a single left-to-right sweep updating all four in order settles the whole answer.

TimeO(n)

SpaceO(1)