题目
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。提示：
0 <= k <= 1000 <= prices.length <= 10000 <= prices[i] <= 1000
解答
使用buy和sale数组进行动态规划，buy[i] 表示进行第 i 次买入操作后的最大利润（初始值为第一天的股票价格的相反数），sale[i] 表示进行第 i 次卖出操作后的最大利润，代码如下：
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<int> buy(k, -prices[0]); // 定义买入的数组，buy[i] 表示进行第 i 次买入操作后的最大利润（初始值为第一天的股票价格的相反数）
vector<int> sale(k); // 定义卖出的数组，sale[i] 表示进行第 i 次卖出操作后的最大利润
for(int i = 1; i < n; ++i) {
buy[0] = max(buy[0], -prices[i]); // 更新第一次买入的最大利润，取当前买入的最大利润和前一天的最大利润中较大的值
sale[0] = max(sale[0], prices[i] + buy[0]); // 更新第一次卖出的最大利润，取当前卖出的最大利润和前一天的最大利润加上当前股票价格的较大值
for(int j = 1; j < k; ++j) {
buy[j] = max(buy[j], sale[j - 1] - prices[i]); // 更新第 j 次买入的最大利润，取当前买入的最大利润和前一次卖出的最大利润减去当前股票价格的较大值
sale[j] = max(sale[j], buy[j] + prices[i]); // 更新第 j 次卖出的最大利润，取当前卖出的最大利润和当前买入的最大利润加上当前股票价格的较大值
}
}
return sale[k - 1]; // 返回最后一次卖出的最大利润
}
};