BM81. 买卖股票的最好时机(二)
题目描述
给定数组 prices，prices[i] 是某只股票第 i 天的价格。 你可以多次买卖该股票，但再次购买前必须卖出之前的股票（同一时刻最多持有一股）。 求最大收益；不能获取收益则返回 0。
输入格式
prices：int 型一维数组，表示每一天的股票价格。
输出格式
返回 int 型，最大收益（不能获利则为 0）。
示例
示例 1
输入：
prices = [8,9,2,5,4,7,1]
输出：
7
说明： 第 1 天买第 2 天卖（+1）、第 3 天买第 4 天卖（+3）、 第 5 天买第 6 天卖（+3），合计 7。
示例 2
输入：
prices = [5,4,3,2,1]
输出：
0
说明： 价格持续下跌，不交易最优。
示例 3
输入：
prices = [1,2,3,4,5]
输出：
4
说明： 第 1 天买、最后一天卖，收益 4；中间当天买当天卖不影响结果。
解题思路
第一步：理解问题本质
可以交易任意多次，但同一时刻只能持有一股。 直觉上「逢低买入、逢高卖出」就能赚到每一段上涨。
第二步：为什么「逐日累加正差价」是对的
考虑从第 i 天持有到第 j 天卖出，收益是 prices[j] - prices[i]。
这个差值恰好等于这段时间里所有相邻两天正差价之和：
prices[j] - prices[i] = Σ (prices[k+1] - prices[k])
因此，只要我们把每对相邻两天的「正差价」全部累加，就不会漏掉任何利润； 负差价则直接跳过（相当于空仓观望）。这本质上把每一段上涨都完整拿下了。
第三步：贪心实现
profit = 0
for i in range(1, n):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
O(n) 时间、O(1) 空间。也可以理解为： 每天都可以「先卖出昨天的、再买入今天的」，所以只要今天比昨天高就赚差价。
完整代码实现
算法可视化 · 逐帧回放这道题的代码19 帧 · 录制输入 [8,9,2,5,4,7,1]
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
"""多次交易：累加所有相邻正差价"""
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
示例推演
以 prices = [8,9,2,5,4,7,1] 为例，逐对比较相邻价格：
| 相邻对 | 差价 | 是否为正 | 累计收益 |
|---|---|---|---|
| 8→9 | +1 | 是 | 1 |
| 9→2 | -7 | 否 | 1 |
| 2→5 | +3 | 是 | 4 |
| 5→4 | -1 | 否 | 4 |
| 4→7 | +3 | 是 | 7 |
| 7→1 | -6 | 否 | 7 |
最终收益 7，与答案一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 贪心累加正差价 | O(n) | O(1) | 推荐 |
| 状态机 DP（持有/空仓） | O(n) | O(1) | 同样 O(1)，思路更通用 |
易错点总结
1. 把「多次交易」当成「多笔独立交易」去枚举
不需要找买卖点，逐日累加正差价即可，避免复杂的区间划分。
2. 忘记「不能获利返回 0」
单调下跌时没有任何正差价，累加结果自然是 0，天然满足要求。
3. 认为「必须持有一天以上」
当天买当天卖收益为 0，不影响结果；但被问到时要知道不禁止。
扩展思考
- 若限定最多 k 笔交易，就用状态机 DP（见 BM82）。
- 若加上手续费或冷冻期，转移方程需要相应调整。