BM82. 买卖股票的最好时机(三)
题目描述
给定数组 prices，prices[i] 是某只股票第 i 天的价格。 你最多可以对该股票进行两笔交易（一笔 = 一次买入 + 一次卖出）， 再次购买前必须卖出之前的股票。求最大收益；不能获利返回 0。
输入格式
prices：int 型一维数组，表示每一天的股票价格。
输出格式
返回 int 型，最大收益（不能获利则为 0）。
示例
示例 1
输入：
prices = [8,9,3,5,1,3]
输出：
4
说明： 第 3 天买第 4 天卖（+2），第 5 天买第 6 天卖（+2），合计 4。
示例 2
输入：
prices = [9,8,4,1]
输出：
0
说明： 价格持续下跌，不交易最优。
示例 3
输入：
prices = [1,2,8,3,8]
输出：
12
说明： 第一笔第 1 天买第 3 天卖（+7），第二笔第 4 天买第 5 天卖（+5），合计 12。
解题思路
第一步：理解问题本质
最多两笔交易，且任意时刻最多持有一股。 「最多」意味着可以只做一笔、甚至不交易。难点在于两笔交易是串行的： 第二笔只能在第一笔卖出之后开始。
第二步：状态机建模
把「手上资产状态」拆成四个阶段，每个阶段维护「该阶段结束后的最大收益」：
| 状态 | 含义 |
|---|---|
buy1 | 完成第一次买入后的收益（账面为负） |
sell1 | 完成第一次卖出后的收益 |
buy2 | 完成第二次买入后的收益 |
sell2 | 完成第二次卖出后的收益 |
每天用当天的价格 p 依次更新这四个状态：
buy1 = max(buy1, -p) # 之前已买入 vs 今天第一次买入
sell1 = max(sell1, buy1 + p) # 之前已卖出 vs 今天第一次卖出
buy2 = max(buy2, sell1 - p) # 之前已买第二次 vs 今天第二次买入
sell2 = max(sell2, buy2 + p) # 之前已卖第二次 vs 今天第二次卖出
四个状态初始化为 -∞，唯一的效果是强制「先买才能卖」。
最终答案是 sell2（也保证至少为 0）。
第三步：为什么「最多两笔」也兼容
初始 sell2 = -∞，但每天都会用 sell2 = max(sell2, buy2 + p) 更新；
即便只做一笔交易，sell2 也能通过 buy2（取自 sell1）继续传递利润，
所以「只做一笔」「不做」都被覆盖，最终回答不会比真实值小。
完整代码实现
算法可视化 · 逐帧回放这道题的代码16 帧 · 录制输入 [8,9,3,5,1,3]
from typing import List
NEG = float('-inf')
class Solution:
def maxProfit(self, prices: List[int]) -> int:
"""最多两笔交易：四状态滚动 DP"""
buy1 = sell1 = buy2 = sell2 = NEG
for p in prices:
buy1 = max(buy1, -p) # 第一次买入：账面 -p
sell1 = max(sell1, buy1 + p) # 第一次卖出
buy2 = max(buy2, sell1 - p) # 第二次买入
sell2 = max(sell2, buy2 + p) # 第二次卖出
return max(sell2, 0)
示例推演
以 prices = [1,2,8,3,8] 为例，四个状态的关键变化：
| 处理 p | buy1 | sell1 | buy2 | sell2 |
|---|---|---|---|---|
| 1 | -1 | 0 | -1 | 0 |
| 2 | -1 | 1 | -1 | 1 |
| 8 | -1 | 7 | -1 | 7 |
| 3 | -1 | 7 | 4 | 7 |
| 8 | -1 | 7 | 4 | 12 |
最后一天 sell2 达到 12：第一笔赚 7，第二笔用 buy2 = 7 - 3 = 4 再赚 5，
合计 12，与答案一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 状态机 DP | O(n) | O(1) | 推荐 |
| 枚举分界点 | O(n²) | O(1) | 不推荐 |
易错点总结
1. 状态初始化成了 0
buy1/buy2 若初始化为 0，会表示「不花钱就买入」，答案偏高。
必须用 -∞，让买入必须先付出成本。
2. 更新顺序
四个状态必须按 buy1 → sell1 → buy2 → sell2 的顺序更新，
因为后面的状态依赖前面刚更新的值。顺序乱了会用到过期状态。
3. 把「最多两笔」当成「必须两笔」
返回 max(sell2, 0)，允许只做一笔或不交易。
扩展思考
- 最多 k 笔交易可以把状态扩成 2k 个（
buy_1..buy_k、sell_1..sell_k）。 - 加入手续费或冷冻期时，只需在买卖转移上减去手续费 / 跳过若干天。