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


  • 0
    D
    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
    
        }
    };
        
        ;

Log in to reply
 

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