# C++ implementation, dynamic programming

• ``````class Solution {
public:
int maxProfit(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];
}
};``````

• The only problem of understanding is the meaning of variable "lowCost". This variable is to determine a possible start of a new transaction. As we know, a new Transaction is possible to gain more profit only when the current price is lower than the previous price. In the previous situation, the profit at that point is the same as the previous point. The minus is help to find the minimum point below the even line of profit of the previous situation.

• The only problem of understanding is the meaning of variable "lowCost". This variable is to determine a possible start of a new transaction. As we know, a new Transaction is possible to gain more profit only when the current price is lower than the previous price. In the previous situation, the profit at that point is the same as the previous point. The minus is help to find the minimum point below the even line of profit of the previous situation.

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