买卖股票的最佳时机 III

🔴 Hard · 🏷️ 数组、动态规划 · LeetCode#123

📖 题目

最多完成两笔交易（不能同时持有多笔），求最大利润。

输入	输出
[3,3,5,0,0,3,1,4]	6（第4天买0第6天卖3赚3，第7天买1第8天卖4赚3）
[1,2,3,4,5]	4（只做一笔就够）
[7,6,4,3,1]	0（不交易）

💡 思路

"最多两次"意味着局部最优不等于全局最优（跟零钱兑换贪心失效是同一个坑），得老实用 DP。

交易过程可以拆成 4 个阶段，每个阶段维护一条独立的状态：第一次买入、第一次卖出、第二次买入、第二次卖出。buy1[i]/sell1[i]/buy2[i]/sell2[i] 表示第 i 天结束时，处于该状态手里最多能有多少钱。

每个状态每天只有两种选择——按兵不动，或者操作一下，取较大的：

buy1[i]  = max(buy1[i-1],  -prices[i])              不动 / 买入花钱
sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i])   不动 / 卖出赚钱
buy2[i]  = max(buy2[i-1],  sell1[i-1] - prices[i])  不动 / 用第一笔利润再买
sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i])   不动 / 卖出赚钱

规律很整齐：每行都是 max(自己昨天的值, 上一行昨天的值 ± price)，buy 行减价格，sell 行加价格。第二次买入依赖第一次卖出的结果（sell1[i-1] - price），这正是"用上一笔的利润去做下一笔"的体现，两笔交易被自然串联起来。

💻 代码

表格版（理解用）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1, sell1, buy2, sell2 = [0]*n, [0]*n, [0]*n, [0]*n
        buy1[0] = buy2[0] = -prices[0]
        for i in range(1, n):
            buy1[i]  = max(buy1[i-1],  -prices[i])
            sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i])
            buy2[i]  = max(buy2[i-1],  sell1[i-1] - prices[i])
            sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i])
        return sell2[-1]

时间复杂度 O(n)，空间复杂度 O(n)。

滚动变量版（每行只依赖前一天，4个数组可以压成4个变量）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for p in prices[1:]:
            buy1  = max(buy1,  -p)
            sell1 = max(sell1, buy1 + p)
            buy2  = max(buy2,  sell1 - p)
            sell2 = max(sell2, buy2 + p)
        return sell2

时间复杂度 O(n)，空间复杂度 O(1)。答案是 sell2——如果交易一次或者根本不交易更优，这个值也会自动覆盖到（不交易时 sell2 保持初始的 0，比其他情况都小就不会被选中）。

这跟打家劫舍的 max(选, 不选) 是同一个套路，只是从 2 个状态（抢/不抢）扩展到了 4 个状态（两轮买卖）。