Best Time to Buy and Sell Stock III

Problem

You are given prices, where prices[i] is the price of a stock on day i. You may complete at most two transactions to maximize your profit. A transaction is one buy followed by a later sell. You may not hold more than one share at a time — you must sell before you buy again — and you never have to trade at all. Return the maximum total profit you can achieve.

Examples

• prices = [3, 3, 5, 0, 0, 3, 1, 4] → 6 — buy at 0 (day 3) sell at 3 (day 5) for +3, then buy at 1 (day 6) sell at 4 (day 7) for +3; total 6.
• prices = [1, 2, 3, 4, 5] → 4 — one transaction (buy 1, sell 5) already captures the whole rise; a second transaction adds nothing.
• prices = [7, 6, 4, 3, 1] → 0 — prices only fall, so the best move is to make no transaction at all.

Constraints

• 1 <= len(prices) <= 10^5
• 0 <= prices[i] <= 10^5
• At most two non-overlapping transactions.
• The 10^5 length forces an O(n) or O(n·k) solution with k = 2; anything that tries all pairs of intervals (O(n²) or worse) times out.

Think about it first

TL;DR

State-machine DP over (day, transactions left, holding?), unrolled into four rolling variables — O(n) time, O(1) space.

The recurrence

Let f(i, t, h) be the most profit obtainable from day i onward, where t = transactions still available and h = 1 if we currently hold a share, else 0. We charge a transaction when we buy.

f(i, t, 0) = max( f(i+1, t, 0),              # rest, still empty-handed
                  f(i+1, t-1, 1) - prices[i] )   # buy today, uses one transaction
f(i, t, 1) = max( f(i+1, t, 1),              # rest, keep holding
                  f(i+1, t, 0) + prices[i] )     # sell today
base:  f(n, ., .) = 0  and  f(i, 0, 0) = 0       # no days left, or no transactions left
answer = f(0, 2, 0)

Approach 1 — Brute force (try every pair of intervals)

Intuition. Two transactions are two non-overlapping (buy, sell) intervals. Enumerate the split day d: take the best single transaction entirely within prices[:d] and the best entirely within prices[d:], and add them. The best single transaction on a slice is the standard “max price minus running min”.

from typing import List

def maxProfit(prices: List[int]) -> int:
    n = len(prices)
    if n < 2:
        return 0

    def best_single(lo: int, hi: int) -> int:      # best in prices[lo:hi]
        min_price, best = float("inf"), 0
        for i in range(lo, hi):
            min_price = min(min_price, prices[i])
            best = max(best, prices[i] - min_price)
        return best

    ans = 0
    for d in range(n + 1):                          # split point
        ans = max(ans, best_single(0, d) + best_single(d, n))
    return ans

Complexity: O(n²) time (n split points × O(n) scan each), O(1) space. With n = 10^5 that is ~10^10 operations — far too slow, which is what the constraint rules out.

Approach 2 — Memoized top-down (the recurrence directly)

The insight: f(i, t, h) depends only on those three small coordinates — i up to n, t in {0,1,2}, h in {0,1} — so there are only O(6n) distinct states. Cache them.

from functools import lru_cache
from typing import List

def maxProfit(prices: List[int]) -> int:
    n = len(prices)

    @lru_cache(maxsize=None)
    def f(i: int, t: int, holding: int) -> int:
        if i == n or t == 0:
            return 0
        rest = f(i + 1, t, holding)
        if holding:
            act = prices[i] + f(i + 1, t, 0)          # sell
        else:
            act = -prices[i] + f(i + 1, t - 1, 1)     # buy (spends a transaction)
        return max(rest, act)

    return f(0, 2, 0)

Complexity: O(n · k · 2) = O(n) time with k = 2, O(n) space for the cache and recursion. Correct and clear, but recursion over 10^5 days risks stack limits — hence the iterative forms below.

Approach 3 — Tabulated bottom-up

The insight: fill the same table iteratively from the last day backward. Keep a (t+1) × 2 grid per day; because day i only reads day i+1, we sweep right-to-left.

from typing import List

def maxProfit(prices: List[int]) -> int:
    n = len(prices)
    K = 2
    # dp[t][h] = best profit from current day onward with t buys left, holding h
    dp = [[0, 0] for _ in range(K + 1)]

    for i in range(n - 1, -1, -1):
        new = [[0, 0] for _ in range(K + 1)]
        for t in range(1, K + 1):
            new[t][0] = max(dp[t][0], -prices[i] + dp[t - 1][1])   # rest / buy
            new[t][1] = max(dp[t][1],  prices[i] + dp[t][0])       # rest / sell
        dp = new
    return dp[K][0]

Complexity: O(n · k) time, O(k) space (two small grids). Iterative, no recursion depth risk.

Approach 4 — Space-optimized four-variable unroll

The insight: with k fixed at 2 there are only four meaningful “in-progress” values, and each only needs the previous day’s numbers. Track them as scalars and update once per day, left to right:

• buy1 = best balance after buying the 1st share (a negative number: cash spent)
• sell1 = best profit after selling the 1st share
• buy2 = best balance after buying the 2nd share (profit from txn 1, minus today’s price)
• sell2 = best total profit after selling the 2nd share

Each day advances through this fixed chain of states:

flowchart LR
    S["Start: no shares"] -->|buy 1st| B1["buy1: holding 1st"]
    B1 -->|sell 1st| A1["sell1: 1st sold"]
    A1 -->|buy 2nd| B2["buy2: holding 2nd"]
    B2 -->|sell 2nd| A2["sell2: 2nd sold (answer)"]

from typing import List

def maxProfit(prices: List[int]) -> int:
    buy1 = buy2 = float("-inf")
    sell1 = sell2 = 0
    for p in prices:
        buy1 = max(buy1, -p)            # buy 1st as cheaply as possible
        sell1 = max(sell1, buy1 + p)    # sell 1st
        buy2 = max(buy2, sell1 - p)     # reinvest txn-1 profit into 2nd buy
        sell2 = max(sell2, buy2 + p)    # sell 2nd
    return sell2

Updating in this fixed order within one loop iteration is intentional: sell1 may use today’s freshly updated buy1, modelling a same-day buy-then-sell, which never hurts (zero-profit) and keeps the transitions correct.

Walkthrough on prices = [3, 3, 5, 0, 0, 3, 1, 4]:

sell2 = 6, matching the expected answer (buy 0→sell 3, buy 1→sell 4).

Complexity: O(n) time, O(1) space — the tightest form.

Common pitfalls

• Initializing buy1/buy2 to 0 instead of -inf: on strictly decreasing prices you’d fabricate a free share and report a phantom profit.
• Double-counting a transaction: charge it on the buy or the sell, never both. Be consistent with your t-1.
• Assuming the two transactions must be far apart — they can be adjacent (sell on day d, buy on the same day d) and even collapse to a single transaction when that’s best (Example 2).
• Trying all O(n²) interval pairs and hoping it’s fast enough — it isn’t at 10^5.

Pattern takeaway

When a problem caps the number of “uses” (transactions, refuels, moves), make that count part of the DP state alongside a small per-step status flag (here: holding or not). Each step is max(rest, act). Once the count is a fixed small constant, you can unroll the state array into a handful of rolling scalars and reach O(1) space — the same trick generalizes directly to the “at most k” version.