188. Best Time to Buy and Sell Stock IV
Say you have an array for which the i-th 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).
Example 1:
Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
这是股票买卖最难的一题！问最多进行k次交易能获得的最大收益是多少。参考网上题解1和题解2。 令mustSell[i][j]表示前i天最多交易j次能获得的最大收益，且第i天必须卖出；globalBest[i][j]表示前i天最多交易j次能获得的最大收益，不要求第i天必须卖出。则有如下递推关系：
- mustSell[i][j]=max(globalBest[i-1][j-1]+profit, mustSell[i-1][j]+profit)
- globalBest[i][j]=max(globalBest[i-1][j], mustSell[i][j])
解释一下，profit=prices[i]-prices[i-1]为第i-1天买入，第i天卖出的收益。
第一个公式中，前i天最多交易j次且第i天卖出的最大收益为“前i-1天最多交易j-1次的全局最大收益+第i-1天买入第i天卖出的收益”与“前i-1天最多交易j次且第i-1天卖出的最大收益+第i-1天买入第i天卖出的收益”的较大者。第一部分好理解，第二部分为什么还是j次交易呢，第一眼看上去好像有j+1次交易了，但是因为mustSell[i-1][j]表示第i-1天必须卖出，而profit表示第i-1天要买入，第i天卖出，两者加起来的效果相当于第i-1天的卖出买入抵消了，即交易次数还是j次，而且恰好变成了第i天卖出，和mustSell[i][j]的含义一致。
第二个公式就好理解了，前i天最多交易j次的全局最大收益为“最后一次交易不在第i天发生，则globalBest[i-1][j]”与“最后一次交易在第i天发生，则mustSell[i][j]”的较大者。
如果允许交易的次数k很大，那么以上DP效率较低，可以换成LeetCode Best Time to Buy and Sell Stock II的贪心策略。因为一次交易至少涉及到两天，所以如果k>=prices.size()/2时，可以采用贪心策略。
完整代码如下：
class Solution {
public:
int maxProfit(int k, vector<int>& prices)
{
int days = prices.size();
if (days < 2)
return 0;
if (k >= days / 2) {
int ans = 0;
for (int i = 1; i < days; ++i) {
if (prices[i] > prices[i – 1])
ans += (prices[i] – prices[i – 1]);
}
return ans;
}
vector<vector<int> > mustSell(days, vector<int>(k + 1, 0)), globalBest(days, vector<int>(k + 1, 0));
for (int i = 1; i < days; ++i) {
int profit = prices[i] – prices[i – 1];
for (int j = 1; j <= k; ++j) {
mustSell[i][j] = max(globalBest[i – 1][j – 1] + profit, mustSell[i – 1][j] + profit);
globalBest[i][j] = max(globalBest[i – 1][j], mustSell[i][j]);
}
}
return globalBest[days – 1][k];
}
};本代码提交AC，用时9MS。