BM81　买卖股票的最好时机(二)¶

中等通过率 62.53%python3核心代码模式样例通过牛客 AC贪心动态规划

讲解章节：线性 DP

一句话

不限交易次数，把每一段上涨都吃掉：相邻差为正就累加。

解题思路¶

这题考什么¶

交易次数不限、且卖出当天可以立刻再买入，这两条合起来让收益可以任意拆分：

prices[j] - prices[i] = (p[i+1]-p[i]) + (p[i+2]-p[i+1]) + ... + (p[j]-p[j-1])

也就是说，任何一段「低买高卖」的收益都等于它跨过的相邻日差值之和。既然拆分自由，最优策略就是把所有为正的相邻差值全部收进来、把负的全部跳过（那两天不持仓）。这就是贪心解：

ans = 所有 max(0, prices[i] - prices[i-1]) 之和

对应的 DP 视角是两个状态：

hold[i]  = 第 i 天结束时持股的最大收益
empty[i] = 第 i 天结束时空仓的最大收益

转移方程：

hold[i]  = max(hold[i-1],  empty[i-1] - prices[i])
empty[i] = max(empty[i-1], hold[i-1]  + prices[i])

初值 hold[0] = -prices[0]、empty[0] = 0，答案 empty[n-1]。与 BM80 的唯一差别是买入那一步从 empty[i-1] 起算而不是从 0 起算—— 「交易次数」这一维在这里被彻底放开，于是不必记录已经做了几笔。可以证明它与上面的贪心累加恒等；贪心写法只用一个累加器，常数最小。

数据规模与复杂度¶

1 <= n <= 1e5（备注给到 2e5），1 <= prices[i] <= 1e4，时限 2 秒（其他语言）。单趟扫描，时间 O(n)、空间 O(1)，达到题面进阶要求。收益上界不超过 2e5 * 1e4 = 2e9，Python 整数不受字长限制。

坑在哪¶

「当天卖出可以当天再买入」是拆分成立的前提。若题目改成卖出后要冷冻一天，相邻差值就不能自由拼接，贪心立刻失效，必须回到带状态的 DP。
这不是 BM80 那道题：不能只找一次最大差值。[1,2,1,2] 的答案是 2 而不是 1。
反过来也不能把这里的贪心搬去 BM80——那里只允许一笔交易。三道股票题的差别全在「交易次数」这一维上，转移式的其余部分是一样的。
相邻差为 0 时加不加都一样，判 d > 0 少做一次无谓的累加。
循环从下标 1 起步；n 为 0 或 1 时循环体一次都不进，返回 0。

样例复核¶

[8,9,2,5,4,7,1]：正的相邻差是 +1（8->9）、+3（2->5）、+3（4->7），合计 7，与期望输出一致。

参考实现¶

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


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total = 0                       # 一次都不交易也有 0，所以结果不会是负数
        # 从下标 1 起步逐日看相邻差：收益可以拆成相邻差之和，正的全收、负的全跳过
        for i in range(1, len(prices)):
            d = prices[i] - prices[i - 1]
            if d > 0:                   # 等于 0 时收不收都一样，跳过省一次加法
                total += d
        return total

BM81 买卖股票的最好时机(二)¶