```
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (k >= prices.size()/2) {
int res = 0;
for (int i = 1; i < prices.size(); ++i)
res += max(prices[i] - prices[i-1], 0);
return res;
}
int n = k * 2 + 1;
vector<int> dp(n, 0);
for (int i = 1; i < n; i += 2) {
dp[i] = INT_MIN;
}
for (int price : prices) {
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i], dp[i - 1] + (i&1 ? (-1 * price) : price));
}
}
return dp[n - 1];
}
};
```

if you have trouble to understand this solution, please read the following code for Best Time to Buy and Sell Stock |||. It is simple version of this DP solution.

```
int maxProfit(vector<int>& prices) {
//It's wrong if you choose the minimum price for buy2 , but you can maximize the left money.
//
int buy1 = INT_MIN, sale1 = 0, buy2 = INT_MIN, sale2 = 0;
for(int i=0; i<prices.size(); i++){ //the more money left, the happier you will be
buy1 = max(buy1, -prices[i]); //left money after buy1
sale1 = max(sale1, prices[i] + buy1); //left money after sale1
buy2 = max(buy2, sale1 - prices[i]); //left money after buy2
sale2 = max(sale2, prices[i] + buy2); //left money after sale2
}
return sale2;
}
```

I think the test case with k = 1000000000 does not necessary. It asks programer add

```
if (k >= prices.size()/2) {
int res = 0;
for (int i = 1; i < prices.size(); ++i)
res += max(prices[i] - prices[i-1], 0);
return res;
}
```

to rule out this case which alloc too much memory. But I do not think it is contribute anything for the algorithm.