Best Time to Buy and Sell Stock IV
最后更新于：2022-04-01 22:57:22
**一. 题目描述**
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
**二. 题目分析**
这一题的难度要远高于前面几题，需要用到动态规划，代码参考了博客：[http://www.cnblogs.com/grandyang/p/4295761.html](http://www.cnblogs.com/grandyang/p/4295761.html)
这里需要两个递推公式来分别更新两个变量`local`和`global`，然后求至少`k`次交易的最大利润。我们定义`local[i][j]`为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义`global[i][j]`为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：
`local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)`
`global[i][j] = max(local[i][j], global[i - 1][j])`
**三. 示例代码**
~~~
#include
#include
#include
#include
#include
using namespace std;
class Solution {
public:
int maxProfit(int k, vector &prices) {
if(prices.empty() || k == 0)
return 0;
if(k >= prices.size())
return solveMaxProfit(prices);
vector global(k + 1, 0);
vector local(k + 1, 0);
for(int i = 1; i < prices.size(); i++) {
int diff = prices[i] - prices[i - 1];
for(int j = k; j >= 1; j--) {
local[j] = max(local[j] + diff, global[j - 1] + max(diff, 0));
global[j] = max(global[j], local[j]);
}
}
return global[k];
}
private:
int solveMaxProfit(vector &prices) {
int res = 0;
for(int i = 1; i < prices.size(); i++) {
int diff = prices[i] - prices[i - 1];
if(diff > 0)
res += diff;
}
return res;
}
};
~~~
**四. 小结**
参考链接：[http://www.cnblogs.com/grandyang/p/4295761.html](http://www.cnblogs.com/grandyang/p/4295761.html)
';