LeetCode 188. 买卖股票的最佳时机 IV（C语言详解 + 通用模板）

一、题目描述

给定一个整数数组prices和一个整数k，其中prices[i]表示第i天的股票价格。

你最多可以完成k笔交易（每次交易包含一次买入和一次卖出），求最大利润。

注意：不能同时进行多笔交易（必须先卖出再买入）。

二、核心思路（动态规划）

这题是股票系列中最通用的一题（终极版）。

1️⃣ 关键优化（必须想到）

当：

k >= pricesSize / 2

👉 问题等价于：不限次数交易（LeetCode 122）

因为最多只能进行n/2次完整交易。

2️⃣ 状态定义

我们定义两个数组：

• buy[j]：第 j 次买入后的最大利润

• sell[j]：第 j 次卖出后的最大利润

3️⃣ 状态转移

每天遍历价格price：

buy[j] = max(buy[j], sell[j-1] - price); sell[j] = max(sell[j], buy[j] + price);

4️⃣ 初始化

buy[j] = INT_MIN; sell[j] = 0;

三、完整 C 代码

#include <limits.h> int maxProfit(int k, int* prices, int pricesSize) { if (pricesSize == 0 || k == 0) return 0; // 情况1：等价于无限次交易 if (k >= pricesSize / 2) { int res = 0; for (int i = 1; i < pricesSize; i++) { if (prices[i] > prices[i - 1]) { res += prices[i] - prices[i - 1]; } } return res; } int buy[k + 1]; int sell[k + 1]; for (int j = 0; j <= k; j++) { buy[j] = INT_MIN; sell[j] = 0; } for (int i = 0; i < pricesSize; i++) { for (int j = 1; j <= k; j++) { if (buy[j] < sell[j - 1] - prices[i]) { buy[j] = sell[j - 1] - prices[i]; } if (sell[j] < buy[j] + prices[i]) { sell[j] = buy[j] + prices[i]; } } } return sell[k]; }

四、举例分析

示例：

k = 2 prices = [3,2,6,5,0,3]

过程：

1. 第2天买入（2），第3天卖出（6）→ 利润 4

2. 第5天买入（0），第6天卖出（3）→ 利润 3

总利润 =7

五、核心理解（非常关键）

整个过程可以看成：

buy[1] → 第一次买 sell[1] → 第一次卖 buy[2] → 第二次买 sell[2] → 第二次卖 ...

状态链：

sell[0] = 0 ↓ buy[1] ↓ sell[1] ↓ buy[2] ↓ sell[2] ...

👉 本质就是“多阶段状态机”。

六、和其他股票问题的关系（重点总结）

👉 可以统一为一套模板！

七、复杂度分析

• 时间复杂度：O(n * k)

• 空间复杂度：O(k)

八、总结（面试重点）

这题最重要的三点：

1. 想到 k ≥ n/2 → 贪心优化

2. 理解 buy/sell 状态机

3. 掌握通用模板（可解决所有股票问题）

九、一句话总结

👉 股票问题本质：
“第 j 次买/卖的最优状态转移”