题目描述
可以多次买入卖出(手里最多持一股)，求最大总利润。
prices = [7, 1, 5, 3, 6, 4]
输出 = 7 （1→5 赚4，3→6 赚3）
思路解析
把所有「今天 − 昨天 > 0」的差累加起来，就是最大利润。等价于：所有上涨区间的涨幅之和——涨就持有、跌就空仓。
7 → 1 · 跌：第1天到第2天，价格从7跌到1，差为负，不操作。
1 → 5 · 涨：1涨到5，差+4，吃下！累计利润4。（相当于第2天买、第3天卖）
5 → 3 · 跌：5跌到3，负差跳过（先卖掉，空仓等待）。
3 → 6 · 涨：3涨到6，差+3，吃下！累计7。
6 → 4 · 跌：最后6跌到4，跳过。总利润 = 4 + 3 = 7。
一段连续上涨（如1→5）拆成每天的差，总和不变。所以「每个正的日差都拿」= 全局最优——这就是贪心能成立的原因。
参考代码（Python）
Python
1profit = 0
2for i in range(1, len(prices)):
3 if prices[i] > prices[i-1]: # 涨了
4 profit += prices[i] - prices[i-1] # 吃下这段涨幅
5return profit复杂度分析
- 时间复杂度：O(n) —— 扫一遍
- 空间复杂度：O(1) —— 一个变量
套路模板
记住骨架：相邻两步算增量、只累加正的。前提是「操作次数不限、收益可分段独立」，否则不能这么贪。
Python
1# 「无限次操作、累加每步收益」的贪心
2total = 0
3for i in range(1, n):
4 gain = 收益(i-1, i)
5 if gain > 0: total += gain # 只拿正收益
6return total易错点
- ❌ 去找全局最低买、最高卖 → ✅ 累加每段正涨幅即可（多次交易下，分段累加才是最优）
- ❌ 把这套用在「只能交易一次」 → ✅ 一次交易要用 LC121 维护最低价（次数受限时不能简单累加）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。