C++ 3ms O(n) 6 lines DP solution


  • 0
    int maxProfit(vector<int>& prices) {
            // has: we have stock in hand at end of day
            // no: we don't have stock in hand at end of day
            // has1 and no1: states of the day before yesterday
            // has2 and no2: states of yesterday
            int has1, no1 = 0, has2 = INT_MIN, no2 = 0; 
            
            for (int p : prices) {
                // newHas: either 
                //  (1) purchase the stock today (in this case we must cooled down yesterday), or 
                //  (2) keep the stock from yesterday
                // newNo: either 
                //  (1) sell the stock today, or 
                //  (2) cool down while we don't have any stock in hand from yesterday
                int newHas = max(no1 - p, has2), newNo = max(has2 + p, no2);
                has1 = has2, no1 = no2, has2 = newHas, no2 = newNo;     // update states
            }
            
            return no2;
    }
    

Log in to reply
 

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