# C++ DP solution with explanation

• ``````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
sale1 = max(sale1, prices[i] + buy1);                //left money after sale1
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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.