# Dynamic programming with C++ implementation

• ``````class Solution {
private:
int maxProfitHelper(int k, vector<int> prices) {
int n = prices.size();
if(n<=1 || k<1)
return 0;

int temp = 0;
int count = 0;
int i;
for(i=1; i<n; i++)
{
if(prices[i] - prices[i-1] > 0)
{
temp = temp + prices[i] - prices[i-1];
count = count + 1;
}
}

if(count < k)
return temp; // When k is big, dynamic programming might become time consuming

// Dynamic programming
vector<int> curProfit(n, 0);
vector<int> preProfit(n, 0);

int lowCost;
int j;
for(j=0; j<k; j++)
{
lowCost = prices[0];
for(i=1; i<n; i++)
{
if(curProfit[i-1] < prices[i] - lowCost)
curProfit[i] = prices[i] - lowCost;
else
curProfit[i] = curProfit[i-1];

if(prices[i]-preProfit[i-1] < lowCost)
lowCost = prices[i]-preProfit[i-1];
}
preProfit = curProfit;
}
return curProfit[n-1];
}
public:
int maxProfit(vector<int>& prices) {
return maxProfitHelper(2, prices);
}
};``````

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