My simple C++ DP soluton (8ms)


  • 3
    D

    It is still similar to the previous stock problems: use DP and define an array of states to track the maximum margin that state can make.

    • states[0] : no buy/sell operation at all, so always 0
    • states[1] : one buy/no sell
    • states[2] : one buy/one sell
      ...
    • states[2i] : i buy/i sell
    • states[2i+1] : i+1 buy/i sell
      ...

    One trick to play is to maximize the margin, all buy operations should be executed at local minimum points and all sell operations should be executed at local maximum points. So first the function findMinMax is called to detect local min and local max (save minP and maxP) and calculate sum(maxP-minP). If the number of local maximum points is no larger than k, then we should operate at all the maxP points and the maximum margin we can make is sum(maxP-minP). Otherwise, we need to run DP via a finite state machine using the state definition provided as above. The FSM is implemented in the function FSM_stock. Hopefully, the size of maxP is much less than the size of prices, so we can reduce the execution time.

    class Solution {
    private:
        int findMinMax(const vector<int>& prices, vector<int>& minP, vector<int>& maxP)
        {
            int i, len = prices.size(), res = 0;
            for(i=0; i<len-1; i++)
            {
                while(i<len-1 && prices[i+1] <= prices[i]) i++; // detect the local minimum points
                if(i<len-1) minP.push_back(prices[i]);
                else break;
                while(i<len-1 && prices[i+1] >= prices[i]) i++; // detect the local maximum points
                maxP.push_back(prices[i]);
                res +=maxP.back()-minP.back(); // res  = sum(maxP - minP), the maximum margin we can make
            }
            return res;
        }
        
        int FSM_stock(vector<int>& minP, vector<int>& maxP, int k)
        {
                int states[2][1+2*k], i, j, cur =0, next =1, res =0, numMax = maxP.size();
                fill_n(&states[0][1], 2*k, INT_MIN/2);
                states[0][0] = states[1][0] = 0;
    
                for(i=0; i<numMax;++i)
                {
                    for(j=0; j<k; ++j)  
                    { // only buy at the local minimum points
                        states[next][j*2+1] = max(states[cur][j*2+1], states[cur][j*2]-minP[i]); 
                        states[next][j*2+2] = states[cur][j*2+2];
                    }
                    swap(cur, next);
                    for(j=1; j<=k; ++j) 
                    { // only sell at the local maximum points
                        states[next][j*2] = max(states[cur][j*2], states[cur][j*2-1] + maxP[i]);
                        states[next][j*2-1] = states[cur][j*2-1];
                    }
                    swap(cur, next);
                }
                for(i=1; i<=k;++i) res = max(res, states[cur][i*2]);
                return res;
        }
        
    public:
        int maxProfit(int k, vector<int>& prices) {
    
            vector<int> minP, maxP;
            
            int res = findMinMax(prices, minP, maxP);
            if(maxP.size() <= k) return res;
            else
                return FSM_stock(minP, maxP, k);
        }
    };

  • 0
    A

    Thanks a lot for the post. Great coding!!


Log in to reply
 

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