Leetcode 188. Best Time to Buy and Sell Stock IV (Hard) (cpp)
2016-12-29       个评论    来源：闷声大发财
我要投稿

Leetcode 188. Best Time to Buy and Sell Stock IV (Hard)(cpp)

Tag: Dynamic Programming

Difficulty: Hard

```/*

188. Best Time to Buy and Sell Stock IV (Hard)

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).

*/
class Solution {
public:
int maxProfit(int k, vector& prices) {
if (prices.size() < 2) {
return 0;
}
int res = 0;
if (k >= prices.size() / 2) {
for (int i = 1; i < prices.size(); i++) {
if (prices[i] > prices[i - 1]) {
res += prices[i] - prices[i - 1];
}
}
}
else {
vector cur(k + 1), glo(k + 1);
for (int i = 0; i < prices.size() - 1; i++) {
int increase = prices[i + 1] - prices[i];
for (int j = k; j >= 1; j--) {
cur[j] = max(glo[j - 1] + max(increase, 0), cur[j] + increase);
glo[j] = max(glo[j], cur[j]);
}
}
res = glo.back();
}
return res;
}
};```