一、题目描述给定一个整数数组prices和一个整数k其中prices[i]表示第i天的股票价格。你最多可以完成k笔交易每次交易包含一次买入和一次卖出求最大利润。注意不能同时进行多笔交易必须先卖出再买入。二、核心思路动态规划这题是股票系列中最通用的一题终极版。1️⃣ 关键优化必须想到当k pricesSize / 2 问题等价于不限次数交易LeetCode 122因为最多只能进行n/2次完整交易。2️⃣ 状态定义我们定义两个数组buy[j]第 j 次买入后的最大利润sell[j]第 j 次卖出后的最大利润3️⃣ 状态转移每天遍历价格pricebuy[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]过程第2天买入2第3天卖出6→ 利润 4第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] ... 本质就是“多阶段状态机”。六、和其他股票问题的关系重点总结题号限制解法1211 次交易记录最小值122无限次贪心1232 次交易固定 2 组 buy/sell188k 次交易通用 DP本题 可以统一为一套模板七、复杂度分析时间复杂度O(n * k)空间复杂度O(k)八、总结面试重点这题最重要的三点想到 k ≥ n/2 → 贪心优化理解 buy/sell 状态机掌握通用模板可解决所有股票问题九、一句话总结 股票问题本质“第 j 次买/卖的最优状态转移”
LeetCode 188. 买卖股票的最佳时机 IV（C语言详解 + 通用模板）
发布时间：2026/7/9 5:23:21
一、题目描述给定一个整数数组prices和一个整数k其中prices[i]表示第i天的股票价格。你最多可以完成k笔交易每次交易包含一次买入和一次卖出求最大利润。注意不能同时进行多笔交易必须先卖出再买入。二、核心思路动态规划这题是股票系列中最通用的一题终极版。1️⃣ 关键优化必须想到当k pricesSize / 2 问题等价于不限次数交易LeetCode 122因为最多只能进行n/2次完整交易。2️⃣ 状态定义我们定义两个数组buy[j]第 j 次买入后的最大利润sell[j]第 j 次卖出后的最大利润3️⃣ 状态转移每天遍历价格pricebuy[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]过程第2天买入2第3天卖出6→ 利润 4第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] ... 本质就是“多阶段状态机”。六、和其他股票问题的关系重点总结题号限制解法1211 次交易记录最小值122无限次贪心1232 次交易固定 2 组 buy/sell188k 次交易通用 DP本题 可以统一为一套模板七、复杂度分析时间复杂度O(n * k)空间复杂度O(k)八、总结面试重点这题最重要的三点想到 k ≥ n/2 → 贪心优化理解 buy/sell 状态机掌握通用模板可解决所有股票问题九、一句话总结 股票问题本质“第 j 次买/卖的最优状态转移”
)
)
