Short js solution with bit of thinking


  • 0
    F
    var maxProfit = function(prices) {
        var loc=new Array(len),glo=new Array(len),len=prices.length; 
        if(len<=1)
            return 0;
        loc[0]=0,glo[0]=0;
        for(i=1;i<len;i++){
           loc[i]=Math.max((glo[i-3]||0)+(prices[i]-prices[i-1]),loc[i-1]+(prices[i]-prices[i-1]));
           glo[i]=Math.max(loc[i],glo[i-1]);
        }
        return glo[len-1];
    };
    

    Loc store the local min when index i must be included in the final operation(either start new buy-sell cycle and sell in i or continue the previous buy-sell cycle)
    glo store the global min
    it take liner time complexity but need n(2len) storage.
    It a bit like the problem Best Time to Buy and Sell Stock IV when look close into it.


Log in to reply
 

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