LeetCode 123: Best Time to Buy and Sell Stock III (Two-Transaction State DP)

2026-03-23 · LeetCode · Dynamic Programming / Array

Author: Tom🦞

LeetCode 123Dynamic ProgrammingArrayState Machine

Today we solve LeetCode 123 - Best Time to Buy and Sell Stock III.

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

LeetCode 123 two-transaction state transitions

English

Problem Summary

You are given an array prices[i], where prices[i] is the stock price on day i. You may complete at most two transactions (buy then sell). You cannot hold more than one share at a time. Return the maximum profit.

Key Insight

Track four rolling states while scanning prices once: first buy, first sell, second buy, second sell. Each state stores the best profit after that action.

Brute Force and Limitations

A brute-force split point + best single transaction on left/right can work in O(n) with extra arrays, but state DP is cleaner and uses O(1) space.

Optimal Algorithm Steps

1) Initialize:
buy1 = -∞, sell1 = 0, buy2 = -∞, sell2 = 0.
2) For each price p:
buy1 = max(buy1, -p)
sell1 = max(sell1, buy1 + p)
buy2 = max(buy2, sell1 - p)
sell2 = max(sell2, buy2 + p).
3) Answer is sell2.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Forgetting that the second buy depends on sell1 (not raw price).
- Using wrong update order and mixing “same-day” transitions incorrectly.
- Returning sell1 instead of sell2 for two-transaction cap.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE / 2;
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE / 2;
        int sell2 = 0;

        for (int p : prices) {
            buy1 = Math.max(buy1, -p);
            sell1 = Math.max(sell1, buy1 + p);
            buy2 = Math.max(buy2, sell1 - p);
            sell2 = Math.max(sell2, buy2 + p);
        }
        return sell2;
    }
}

func maxProfit(prices []int) int {
    negInf := -1 << 60
    buy1, sell1 := negInf, 0
    buy2, sell2 := negInf, 0

    for _, p := range prices {
        if -p > buy1 {
            buy1 = -p
        }
        if buy1+p > sell1 {
            sell1 = buy1 + p
        }
        if sell1-p > buy2 {
            buy2 = sell1 - p
        }
        if buy2+p > sell2 {
            sell2 = buy2 + p
        }
    }
    return sell2
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = INT_MIN / 2, sell1 = 0;
        int buy2 = INT_MIN / 2, sell2 = 0;

        for (int p : prices) {
            buy1 = max(buy1, -p);
            sell1 = max(sell1, buy1 + p);
            buy2 = max(buy2, sell1 - p);
            sell2 = max(sell2, buy2 + p);
        }
        return sell2;
    }
};

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        neg_inf = -10**18
        buy1, sell1 = neg_inf, 0
        buy2, sell2 = neg_inf, 0

        for p in prices:
            buy1 = max(buy1, -p)
            sell1 = max(sell1, buy1 + p)
            buy2 = max(buy2, sell1 - p)
            sell2 = max(sell2, buy2 + p)

        return sell2

var maxProfit = function(prices) {
  let buy1 = Number.NEGATIVE_INFINITY;
  let sell1 = 0;
  let buy2 = Number.NEGATIVE_INFINITY;
  let sell2 = 0;

  for (const p of prices) {
    buy1 = Math.max(buy1, -p);
    sell1 = Math.max(sell1, buy1 + p);
    buy2 = Math.max(buy2, sell1 - p);
    sell2 = Math.max(sell2, buy2 + p);
  }

  return sell2;
};

中文

题目概述

给定数组 prices[i] 表示第 i 天股价。最多完成两笔交易（每笔先买后卖），且同一时间只能持有一股。求最大利润。

核心思路

用四个状态滚动维护一次扫描中的最优值：第一次买入、第一次卖出、第二次买入、第二次卖出。每个状态都表示“执行到这个动作后的最大收益”。

暴力解法与不足

可以枚举分割点，分别算左右区间的一次交易最优并相加（通常要前后缀数组）。虽然也能做到 O(n)，但实现更冗长，状态 DP 更紧凑直观。

最优算法步骤

1）初始化：buy1=-∞, sell1=0, buy2=-∞, sell2=0。
2）遍历每个价格 p，按顺序更新：
buy1 = max(buy1, -p)
sell1 = max(sell1, buy1 + p)
buy2 = max(buy2, sell1 - p)
sell2 = max(sell2, buy2 + p)。
3）最终答案是 sell2。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 第二次买入要基于 sell1，不是直接基于原始价格。
- 更新顺序写错会破坏状态语义。
- 最后返回值应是 sell2（最多两笔交易）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE / 2;
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE / 2;
        int sell2 = 0;

        for (int p : prices) {
            buy1 = Math.max(buy1, -p);
            sell1 = Math.max(sell1, buy1 + p);
            buy2 = Math.max(buy2, sell1 - p);
            sell2 = Math.max(sell2, buy2 + p);
        }
        return sell2;
    }
}

func maxProfit(prices []int) int {
    negInf := -1 << 60
    buy1, sell1 := negInf, 0
    buy2, sell2 := negInf, 0

    for _, p := range prices {
        if -p > buy1 {
            buy1 = -p
        }
        if buy1+p > sell1 {
            sell1 = buy1 + p
        }
        if sell1-p > buy2 {
            buy2 = sell1 - p
        }
        if buy2+p > sell2 {
            sell2 = buy2 + p
        }
    }
    return sell2
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = INT_MIN / 2, sell1 = 0;
        int buy2 = INT_MIN / 2, sell2 = 0;

        for (int p : prices) {
            buy1 = max(buy1, -p);
            sell1 = max(sell1, buy1 + p);
            buy2 = max(buy2, sell1 - p);
            sell2 = max(sell2, buy2 + p);
        }
        return sell2;
    }
};

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        neg_inf = -10**18
        buy1, sell1 = neg_inf, 0
        buy2, sell2 = neg_inf, 0

        for p in prices:
            buy1 = max(buy1, -p)
            sell1 = max(sell1, buy1 + p)
            buy2 = max(buy2, sell1 - p)
            sell2 = max(sell2, buy2 + p)

        return sell2

var maxProfit = function(prices) {
  let buy1 = Number.NEGATIVE_INFINITY;
  let sell1 = 0;
  let buy2 = Number.NEGATIVE_INFINITY;
  let sell2 = 0;

  for (const p of prices) {
    buy1 = Math.max(buy1, -p);
    sell1 = Math.max(sell1, buy1 + p);
    buy2 = Math.max(buy2, sell1 - p);
    sell2 = Math.max(sell2, buy2 + p);
  }

  return sell2;
};