此题广为流传，所以不再复述题目，可以查看 LeetCode 188. 买卖股票的最佳时机 IV
写此文的目的是防止学了忘、忘了学，仅记录大概的题解思路，更加详细的思路解析可以查看（均为公众号）：
此题依交易次数的不同，可以分为 一次、无限次、和 k 次三种题目
以下思路、代码均根据 LeetCode 对应题目写出
一次交易
限制一次交易的情况比较简单，因为只能交易一次，所以需要寻找谷值和峰值，两者相减即最大收益
但同时也要注意时间不能倒流，需要顺序遍历数组
C# 代码
public class Solution {
public int MaxProfit(int[] prices) {
if(prices.Length == 0) return 0;
int max = 0, n = prices.Length;
int min = prices[0];
for(int i = 1; i< n; i ++) {
min = min > prices[i] ? prices[i] : min;
max = prices[i] - min > max ? prices[i] - min : max;
}
return max;
}
}
无限次交易
无限次交易也比较简单，遵循一个规则：股价逢涨必卖：
- 如果股价连续几天一直上涨，那么每天都卖与峰值一并卖出所获得的收益是相等的
- 如果股价连续几天一直下跌，那么不卖，没有收益
- 如果股价振荡，那么可以把每一天看作一次连续上涨或者连续下跌，按照前两个规则买卖
最后得出结论：逢涨必卖
C# 代码
public class Solution {
public int MaxProfit(int[] prices) {
if (prices.Length == 0) return 0;
int maxProfit = 0;
for (int i = 1; i < prices.Length; i++)
if (prices[i] > prices[i - 1])
maxProfit += prices[i] - prices[i - 1];
return maxProfit;
}
}
k 次交易
2 次交易也可以并作 k 次交易
k 次交易事情开始变得复杂了，可以有动态规划和贪心这两种理解方式，但产出的代码没有很大的差异
动态规划
动态规划的篇幅较长，可以直接参考 漫画：寻找股票买入卖出的最佳时机（整合版），递推式的推理过程非常清晰
贪心
每次交易有两种操作：买 和 卖，因此就有 2 * k 次收益的变化（建立 2 * k 大小的数组），将这些变化记录下来，每次交易操作时都获取最大值，卖出最后一笔就得到了最大收益
每过一天都模拟在当天价格下进行 k 次交易（遍历一次数据），用 Max 函数记录最大值：
- 买入：之前的收益 – 当前股价
- 卖出：之前的收益 + 当前股价
C# 代码
public class Solution {
public int MaxProfit(int k, int[] prices) {
if (prices.Length == 1 || prices.Length == 0 || k == 0) return 0;
int recordCount = 2 * k; // k 次交易，2k 次买卖操作
int[] profitRecord = new int[recordCount]; //收益记录数组
for (int i = 0; i < recordCount; i += 2) //将 k 次的买入全部设为第一天股价
profitRecord[i] = -prices[0]; //以第一天的股价买入
for (int i = 1; i < prices.Length; i++) {
for (int j = 0; j < recordCount ; j++) {
if (j == 0) profitRecord[j] = Math.Max(profitRecord[j], -prices[i]); //第一天作特殊处理
else if (Convert.ToBoolean(j & 1)) profitRecord[j] = Math.Max(profitRecord[j], profitRecord[j - 1] + prices[i]); //卖出操作，现收益 + 当天股价
else profitRecord[j] = Math.Max(profitRecord[j], profitRecord[j - 1] - prices[i]); //买入操作，现收益 - 当天股价
}
}
return profitRecord[recordCount - 1]; //记录数组最后的元素
}
}
