4ms C++ DP beat 84%

  • 6
    // 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 {
        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

    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.