BM82　买卖股票的最好时机(三)¶

较难通过率 43.17%python3核心代码模式样例通过牛客 AC动态规划

讲解章节：线性 DP

一句话

最多两笔交易，把「做到第几笔」编进状态滚动递推。

解题思路¶

这题考什么¶

交易次数被卡成 2，只按「持股 / 空仓」两态已经不够—— 必须把这是第几笔交易也编进状态。一天结束时人只可能处于五种状态之一：

s0：还没做任何操作             收益恒为 0，不必显式维护
s1：完成第一次买入，持股中
s2：完成第一次卖出，空仓
s3：完成第二次买入，持股中
s4：完成第二次卖出，空仓（全部结束）

状态定义：s1[i] .. s4[i] = 第 i 天结束时处于该状态的最大收益。转移方程（今天要么保持原状态不动，要么从上一个状态迁移过来）：

s1[i] = max(s1[i-1],           0 - prices[i])
s2[i] = max(s2[i-1], s1[i-1] + prices[i])
s3[i] = max(s3[i-1], s2[i-1] - prices[i])
s4[i] = max(s4[i-1], s3[i-1] + prices[i])

五个状态串成一条链，每个状态只能从自己或前一个流入，天然禁止了「同时持有两笔」和「第三笔交易」。BM80 是这条链砍到 s2 为止的特例，BM81 则是把链首尾接成环、次数无限的情形——三道题对照着看，「交易次数」这一维的作用一目了然。

初值：s1 取负无穷（还没买过，任何真实收益都优于它），s2 = s3 = s4 = 0。后三者取 0 而不是负无穷，表示「少做几笔交易总是允许的」，于是答案直接取 s4 即可，不必再和 s2、0 取最大值。实际上每一轮之后必有 s4 >= s2：同一轮里 s3 >= s2 - p 先被更新，紧接着 s4 >= s3 + p >= s2，所以 s4 已经吃掉了「只做一笔」的情形。

数据规模与复杂度¶

1 <= n <= 1e5（备注给到 2e5），1 <= val <= 1e4，时限 2 秒（其他语言）。四个标量滚动，单趟扫描，时间 O(n)、空间 O(1)，达到题面进阶要求。

坑在哪¶

同一天内按 s1 -> s2 -> s3 -> s4 的顺序就地更新是安全的，不需要额外的临时变量。提前更新的 s1 用的是今天的价格买入，被同一天的 s2 用到时等价于「当天买当天卖」，贡献恰好 0，不会凭空多赚。顺序反过来（先算 s4）则会读到昨天的 s3，等价于强行拉开一天，虽然不会算多，却把一部分合法方案漏掉。
s1、s2 的初值不能颠倒：s1 是「已经买入」，还没有任何买入记录时它必须是负无穷； s2 是「已经卖出」，取 0 才能表示「一笔都不做」。 s1 取 0 会等价于免费拿到一手股票。
负无穷用 float("-inf") 即可。它参与加法仍是负无穷，不会像取个很小的负整数那样被后续的加价拉回正数区间。Python 的 int 与 float 可以直接比较，不影响正确性。
答案取 s4 而非 max(s2, s4)：由上面的推导 s4 >= s2 恒成立，「只做一笔」的方案已经被 s4 覆盖。
空数组要挡在前面，否则 s1 会停在负无穷，返回值虽仍是 0，但依赖初值的巧合而非推导；题面保证 n >= 1，这条出口是防御性的。

样例复核¶

[8,9,3,5,1,3]：第一笔在 3 买 5 卖得 2，第二笔在 1 买 3 卖得 2， s4 收在 4，与期望输出一致。

参考实现¶

solutions/nowcoder/BM82/sol.py
from typing import List, Optional


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        NEG = float("-inf")         # 持股状态的初值：加法之后仍是负无穷，不会被价格拉回正数
        buy1, sell1 = NEG, 0        # 第一次买入后 / 第一次卖出后的最大收益
        buy2, sell2 = NEG, 0        # 第二次买入后 / 第二次卖出后的最大收益；0 表示「少做几笔也行」
        for p in prices:
            # 按 buy1 -> sell1 -> buy2 -> sell2 的链序就地更新。
            # 提前更新的量被同一天的下一状态用到时相当于「当天买当天卖」，贡献 0，不会多赚
            if -p > buy1:
                buy1 = -p           # 第一笔买入从 0 起算，等价于记下历史最低价的相反数
            if buy1 + p > sell1:
                sell1 = buy1 + p    # 第一笔卖出
            if sell1 - p > buy2:
                buy2 = sell1 - p    # 第二笔买入必须建立在第一笔已卖出之上
            if buy2 + p > sell2:
                sell2 = buy2 + p    # 第二笔卖出
        return sell2                # 恒有 sell2 >= sell1，「只做一笔」的情形已被覆盖

BM82 买卖股票的最好时机(三)¶