4ms C++ DP beat 84%


  • 6
    X
    // 3 values to update each step:
    //  the most money choosing buy: b;
    //  the most money choosing sell: s0;
    //  the most money doing nothing: s1; 
    
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.size()<=1) return 0;
            int s0=0, s1=0, b=-prices[0];
            for(int i=1; i<prices.size(); i++) {
                int tmp = max(s0, s1);
                s0 = b+prices[i];
                b = max(s0,s1)-prices[i];
                s1 = tmp;
            }
            return max(s0, s1);
            
            
        }
    };

  • 0
    L

    for cool code, we call 66666qifei code in china.~


Log in to reply
 

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