LeetCode 188. 买卖股票的最佳时机 IV
目录
题目描述
题意分析
给一个按天排列的价格数组，最多做 k 笔交易，求最大总收益。一笔交易 = 一次买入加上之后的一次卖出，并且手上任何时刻最多持有一股，也就是必须先卖掉才能再买，交易之间不能重叠。可以一笔都不做，所以答案至少是 0。
约束信号有两个。其一，题目限制的是「次数」，说明除了「当前是否持股」之外，还必须把「已经用掉几笔」也记进状态里，否则无法判断还能不能再买。其二，k 的取值范围与天数无关，k 可以给到 100 甚至更大，而 n 可能只有几十。
第二个信号非常关键：一笔交易至少要占掉一买一卖两天，所以 n 天里最多能做 $\lfloor n/2 \rfloor$ 笔有意义的交易。当 $k \ge \lfloor n/2 \rfloor$ 时，次数限制形同虚设，本题就退化成了 122 题（不限交易次数），直接把所有上涨段的差值加起来即可，不必开 k 那么大的状态数组。
边界方面：
k = 0、价格数组为空、或者只有一天，都返回 0；价格全程单调下降时一笔都不该做，答案也是 0，而不是负数。
解法：交易次数状态动态规划
核心思路
交易次数受限时，仅记录“持股 / 不持股”还不够，还要记录最多允许做几笔交易。对每个交易上限
t = 1...k定义：
buy[t]：处理完当前价格后，最多进行t次买入且手中持股的最大利润；sell[t]：处理完当前价格后，最多完成t次卖出且手中不持股的最大利润。当天只有“保持原状态”或“执行一次操作”两种选择：
\[buy[t] = \max(buy[t],\ sell[t-1] - price)\] \[sell[t] = \max(sell[t],\ buy[t] + price)\]
buy[t]从sell[t-1]转移，保证第t次买入前，前t-1笔交易已经结束；sell[t]则在已有持仓上卖出。循环不变量是：处理完每一天后，两组状态都覆盖该价格前缀内、相应交易上限下的最优利润。因此最后的sell[k]就是最多做k笔交易的答案。还有一个必须先处理的退化情形：
n天最多完成n / 2笔交易（整数除法）。当k >= n / 2时，次数限制已经无效，问题等价于不限次数交易；累加所有正的相邻差值即可。这个分支也避免了k很大时无意义地申请 $O(k)$ 空间。
解题步骤
- 若
k = 0或价格不足两天，直接返回 0。- 若
k >= n / 2，累加所有prices[i] - prices[i-1] > 0的差值并返回。- 初始化
sell[t] = 0、buy[t] = -prices[0]。初始时可以不交易；若持股，只可能按首日价格买入。- 从第二天开始遍历价格，对
t = 1...k更新buy[t]和sell[t]。同一天卖出后再买入或买入后再卖出的收益为 0，不会制造更优解，所以一维原地更新安全。- 返回
sell[k]。“最多k笔”允许少做交易，因此不需要强行完成第k笔。例如
k = 2、prices = [3,2,6,5,0,3]：第一笔在 2 买、6 卖得到 4；随后buy[2]在价格 0 时更新为4-0=4，最后价格 3 时sell[2]=4+3=7。
代码实现
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k == 0 || n < 2) {
return 0;
}
if (k >= n / 2) {
int profit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
for (int t = 1; t <= k; t++) {
buy[t] = -prices[0];
}
for (int i = 1; i < n; i++) {
for (int t = 1; t <= k; t++) {
buy[t] = Math.max(buy[t], sell[t - 1] - prices[i]);
sell[t] = Math.max(sell[t], buy[t] + prices[i]);
}
}
return sell[k];
}
}
func maxProfit(k int, prices []int) int {
n := len(prices)
if k == 0 || n < 2 {
return 0
}
if k >= n/2 {
profit := 0
for i := 1; i < n; i++ {
if prices[i] > prices[i-1] {
profit += prices[i] - prices[i-1]
}
}
return profit
}
buy := make([]int, k+1)
sell := make([]int, k+1)
for t := 1; t <= k; t++ {
buy[t] = -prices[0]
}
for i := 1; i < n; i++ {
for t := 1; t <= k; t++ {
buy[t] = max(buy[t], sell[t-1]-prices[i])
sell[t] = max(sell[t], buy[t]+prices[i])
}
}
return sell[k]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：DP 分支为 $O(nk)$；当
k >= n / 2时，贪心分支为 $O(n)$。- 空间复杂度：DP 分支为 $O(k)$；贪心分支为 $O(1)$。
关键点总结
buy[t]与sell[t]表示“最多t次”，所以sell[k]自然包含少做交易的方案。- 买入必须从
sell[t-1]转移，这是“同一时刻最多持有一股、交易不能重叠”的状态化表达。k >= n / 2时要切换到不限次数的贪心，既降复杂度，也避免超大状态数组。- 一维滚动可行的原因是同日买卖只产生 0 收益，不会改善最优值。
易错点总结
- 买入依赖写错：若从
sell[t]买入，会把交易上限放松；k=1, [1,3,1,3]会错误地得到 4，而正确答案是 2。- 漏掉大
k分支：当k远大于n时，直接创建长度k+1的数组可能内存溢出。- 只写操作、不保留旧状态：转移必须取
max，否则后面的低收益操作会覆盖此前的最优利润。- 贪心累加所有差值：只累加正差值；下降段不参与收益。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 121. 买卖股票的最佳时机 | 简单 | 单次交易维护历史最低价 |
| 122. 买卖股票的最佳时机 II | 中等 | 不限次数贪心累加上涨段 |
| 123. 买卖股票的最佳时机 III | 困难 | 固定两笔交易的四状态机 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | 卖出后加一天冷冻期的状态机 |
| 714. 买卖股票的最佳时机含手续费 | 中等 | 每笔交易扣手续费的两状态机 |
| 剑指 Offer 63. 股票的最大利润 | 中等 | 单次交易的最大差值 |