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

class Solution:
    def maxProfit(self, 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

class Solution:
    def maxProfit(self, 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

class Solution:
    def maxProfit(self, 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

from typing import List

class Solution:
    def maxProfit(self, 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.