# My C++ DP solution O(nk) time and O(K) space and the max_heap version (learned from other posts)

• ``````Again, it is a Viterbi algorithm for a trellis FSM,which has state transitions as
S(2K): for the state that K buys and K sells occur, S(2K+1):  for the state that K+1 buys and K sells occur
S(2K) -> S(2K) (no transaction for stage i) or S(2K)-> S(2K+1) (a buy occurs at stage i)
S(2K+1) -> S(2K+1) (no transaction for stage i) or S(2K+1)-> S(2K+1) (a sell occurs at stage i)
In the below code, maxProfit saves the current maximum profit for each state. The algorithm scans prices[i] and update the FSM according to the state transition. It is a typical Viterbi algorithm that has O(nk) time complexity.

class Solution {
public:
int maxProfit_NL(vector<int> &prices) {
int cost;
int i, pSize = prices.size();
if(pSize < 2) return 0;
else
{
int maxProfit[2] = {0, -prices[0]};
for(i=1;i<pSize;i++)
{
cost = maxProfit[1];
maxProfit[1] = max(maxProfit[0] - prices[i], maxProfit[1]);
maxProfit[0] = max(cost + prices[i], maxProfit[0] );
}

return maxProfit[0];
}

}

int maxProfit(int k, vector<int> &prices) {

int pSize = prices.size();
if(pSize<2) return 0;
else if (k>= pSize/2)  return maxProfit_NL(prices);
else
{
int stateNum = min(pSize/2, k)*2 + 1;
// ping-pang mode to switch between old and new state array
vector<vector<int> > maxProfit(2, vector<int>(stateNum, 0)); // 1: one buy, 2: one sell, 3: two buys, 4:two sells
int i, j, cur = 0 , next;

//initiate the state array
for(i=1; i<stateNum; i=i+2)
{
maxProfit[0][i] = INT_MIN;
}

for(i=0; i<pSize; i++)
{
next = cur ^ 0x1;

for(j=1; j<stateNum; j=j+2)
{
maxProfit[next][j] = max(maxProfit[cur][j], maxProfit[cur][j-1]-prices[i]); // buy
maxProfit[next][j+1] = max(maxProfit[cur][j+1], maxProfit[cur][j]+prices[i]); // sell
}
cur = next;
}
return maxProfit[cur][stateNum-1];
}
}
}
``````

When K is large, then the complexity could be high. As other contributors pointed out, there is another version based on max heap, which gives O(n + Klog(n)) complexity. There are several key tricks in this version
// Find all consecutive local min/max pairs, all the possible transactions can only happen on those points (min for buy and max for sell)
// 1) if a new local min is less than the previous min, then the previous min/max pair can be used to generate a candidate transaction // since the future transaction can not do buy at the previous min (if so, we can always do buy at the current min, which has less cost // 2). if a new local max is bigger than the previous max and the new local min is bigger than the previous min, then we have to switch the current min/max of the current pair and the previous pair to two new pairs (previous min, current max) and (current min, previous max). The reason to do so is to guarantee that the bigger profit (i.e. (previous min, current max)) is considered and the new two pairs can generate the same profits as the original one. This guarantees that if only one transaction is needed, then the bigger one will be selected. If two transactions are needed, it gives the same profit as the original one.

``````class Solution {
public:
int maxProfit_NL(vector<int> &prices) {
int cost;
int i, pSize = prices.size();
if(pSize < 2) return 0;
else
{
int maxProfit[2] = {0, -prices[0]};
for(i=1;i<pSize;i++)
{
cost = maxProfit[1];
maxProfit[1] = max(maxProfit[0] - prices[i], maxProfit[1]);
maxProfit[0] = max(cost + prices[i], maxProfit[0] );
}

return maxProfit[0];
}

}

int maxProfit(int k, vector<int> &prices) {

int pSize = prices.size(); // vector size
stack<pair<int, int>> minmaxS;
int minP, maxP; // local max peak
vector<int> profit; // all possible profits
int res =0;
int i=1;
pair<int, int> topNode;

if(pSize<2) return 0; // less than 2 days, no transaction possible
else if (k>= pSize/2)  return maxProfit_NL(prices); // no limit on the number of transactions, Viterbi (DP) with 2 states
else
{ //
while(i<pSize)
{// search for local min/max pair
while( (i<pSize) && (prices[i] <= prices[i-1])) i++;
minP = prices[i-1]; // min peak
while( (i<pSize) && (prices[i] >= prices[i-1])) i++;
maxP = prices[i-1]; // max peak

// if the current min less than the last min, so save the profit of the last min/max pair since the following pairs will not start from a point before the current min
while( (!minmaxS.empty()) && (minP <= (topNode = minmaxS.top()).first) )
{
profit.push_back(topNode.second - topNode.first); // the first pair doesn't need to save
minmaxS.pop();
}
// if the current max is larger than the last max, so we have to switch the last minmax pair and the current one to generate a bigger profit
while( (!minmaxS.empty()) && (maxP >= (topNode = minmaxS.top()).second) )
{
profit.push_back(topNode.second - minP); // switch the min value
minP = topNode.first;
minmaxS.pop();
}
minmaxS.push(make_pair(minP, maxP));
} // end of while

while(!minmaxS.empty())
{
topNode = minmaxS.top();
profit.push_back(topNode.second - topNode.first); // switch the min value
minmaxS.pop();
}

if(profit.size()<=k)
{
for(i=0; i<profit.size(); i++) res +=profit[i];
}
else
{ // use heap to get the first k biggest profits
std::make_heap(profit.begin(), profit.end());
for(i=0; i<k; i++)
{
pop_heap(profit.begin(), profit.end());
res += profit.back();
profit.pop_back();
}
}

return res;
}// end of else

}
};

;``````

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