买卖股票 II:每一段上涨都装进口袋
可以买卖很多次,但同一天卖完还能再买。后一天比前一天高,这个差价就可以单独赚到。全部正差价加起来就是最大利润。
从第二天起,若 prices[i] > prices[i-1],把差值累进答案。允许同一天卖出再买入,所以一段连续上涨拆成相邻小段,总和不变。时间 O(n),空间 O(1)。
数组 prices[i] 是第 i 天的股价。你可以在任意天买入、任意天卖出,次数不限,但手里最多同时持有一股,必须先卖再买。求能赚到的最大利润。不交易利润是 0,不会亏到负数。
主例 prices = [7, 1, 5, 3, 6, 4]。在价格 1 买入、5 卖出赚 4,再在 3 买入、6 卖出赚 3,一共 7。只做一笔 1 买 6 卖只有 5,不如拆成两笔。
和 LC121 不同:121 全程只能买卖一次。本文要回答:为什么把每一段相邻上涨都吃掉就是全局最优,以及主例五次相邻比较里哪两次真正进账。
相邻上涨全部变现
第一直觉是沿用 121:找一个最低点买、一个最高点卖。主例最低 1、最高 6,利润 5,小于 7。题目允许卖完再买,1 到 6 中间那个 5 跌到 3 的凹陷,其实可以先在 5 离场,再在 3 上车,把两段上升都收走。
缺的是「同一天卖出再买入」这条许可。它意味着:一段连续上涨 1→5→8,拆成 (5-1)+(8-5) 和直接 8-1 一样多。于是不必寻找整段波峰波谷,只要看相邻两天:后一天更高,差价就入袋;后一天更低或持平,这笔不做。所有正的相邻差加起来,等于把每一段上升都独立变现。
为什么这就是最优:下跌段做交易只会亏;持平段利润是 0。任意一个跨过凹陷的大买卖,利润都不超过拆开后两段上升之和。所以贪心加相邻正差,不会丢掉更好的策略,也不会多算。
用手走主例。i=1,7 跌到 1,差是负的,利润 0,演示第一帧。i=2,1 涨到 5,加 4,利润 4。i=3,5 跌到 3,不动,利润仍 4。
i=4,3 涨到 6,加 3,利润 7。i=5,6 跌到 4,不动。答案 7,对应「1 买 5 卖」加「3 买 6 卖」。演示六帧就是这五次相邻比较加上收尾。
全程下跌时每一个差都是负的,利润停在 0,不要做成「最不亏的那一笔」。只有一天时没有相邻对,利润 0。手续费或冷冻期会让「拆成相邻小段」不再免费,那是 714、309 的约束;本题没有这些摩擦,相邻正差可以直接加。
拆解大买卖连续上涨 [a,b,c] 的利润 (c−a) 等于 (b−a)+(c−b)。允许当天卖再买,拆开不损失、也不多赚。主例若死抱 1 到 6,会少收凹陷左侧已经涨完的那 4。
Go:相邻上涨累加
func maxProfit(prices []int) int {profit := 0for i := 1; i < len(prices); i++ {if d := prices[i] - prices[i-1]; d > 0 {profit += d}}return profit}
1只看相邻两天。d>0 才加,下跌和持平都跳过。
2主例五次比较里,只有 1→5 和 3→6 进账,4+3=7。
3profit 从 0 起,全程下跌不会变成负数。不必真的模拟持仓变量。
总结
可以多次买卖时,把所有相邻上涨加起来。主例 4+3=7。
- 121 只能一笔,主例会停在 5。本题允许卖完再买,凹陷两侧都要收。
- 连续上涨拆成相邻小段,总和不变。下跌段不加。
- 有手续费或冷冻期就不能这样拆。没有交易摩擦时,贪心等于最优。