买卖股票最佳时机 III

[!abstract] 问题 最多交易 2 次，不能同时持有多股。

示例

输入: prices = [3,3,5,0,0,3,1,4]
输出: 6
解释:
- 第1次交易: 买入(3)，卖出(5)，利润=2
- 第2次交易: 买入(0)，卖出(3)，利润=3
- 总利润=6

解法

DP 空间优化

function maxProfit(prices: number[]): number {
  let buy1 = -prices[0], sell1 = 0;
  let buy2 = -prices[0], sell2 = 0;

  for (let i = 1; i < prices.length; i++) {
    buy1 = Math.max(buy1, -prices[i]);                    // 第一次买入
    sell1 = Math.max(sell1, buy1 + prices[i]);            // 第一次卖出
    buy2 = Math.max(buy2, sell1 - prices[i]);             // 第二次买入
    sell2 = Math.max(sell2, buy2 + prices[i]);            // 第二次卖出
  }

  return sell2;
}

状态解释

状态	含义
buy1	第一次买入后的最大收益
sell1	第一次卖出后的最大收益
buy2	第二次买入后的最大收益
sell2	第二次卖出后的最大收益

复杂度

时间	空间
O(n)	O(1)

---

参见: **股票问题** | **买卖股票最佳时机II** | **买卖股票最佳时机IV**