Why re-using code for #121 may fail here. Explanation and thinking process included.


  • 0
    L

    My first thought is to re-use the code that is used to solve #121, in a big for loop. It is however an O(n^2) solution and exceeds the time limits. (see explanation below, namely the calc function at the bottom and the for loop that's commented out)

    var maxProfit = function(prices) {
        
        if(prices.length < 2) {
            return 0;
        }
        if(prices.length == 2) {
            return Math.max(0, prices[1] - prices[0]);
        }
        
        
        var maxProfit = 0;
        var frontProfit = [];
        var backProfit = [];
        var sellPrice;
    
    // The reason the approach is not efficient is because it calculates many values that has been calculated.
    // For example, to calculate frontProfit[10], frontProfit[9] and [8] and so on till [0] will ALL be calculated again,
    // and these side-product values will not be stored again because they are written in the array already.
    // The complexity is O(n^2), inefficient
        // for(var i = 0; i < prices.length; i++) {
        //     // var pro = calc(prices, 0, i) + calc(prices, i, prices.length);
        //     // maxProfit = Math.max(pro, maxProfit);
        //     frontProfit[i] = calc(prices, 0, i);
        //     backProfit[i] = calc(prices, i, prices.length);
        // }
        
        
        // use an index i to divide the entire array into two parts: front and back
        // calculate the max profit using 1 (or fewer) transaction between day 0 thru day i (variable)
        // store the results in another array
        
        // for example
        // array:   1 4 2   or  1  15   4 100  90 100
        // front:   0 3 3   or  0  14  14  99  99  99
        // back:    3 0 0   or 99  96  96  10  10   0
        // max=f+b: 3 3 3   or 99 110 110 109 109  99
        // Note: front[0] and back[len-1] are pre-set to 0
        
        var buyPrice = prices[0];
        var maxDiff = 0;
        frontProfit[0] = 0;
    
        for(var i = 1; i < prices.length; i++) {
            frontProfit[i] = frontProfit[i-1];
            var diff = prices[i] - buyPrice;
            if(diff > maxDiff) {
                maxDiff = diff;
                sellPrice = prices[i];
                frontProfit[i] = maxDiff;
            }
            // decreasing interval
            if(diff < 0) {
                buyPrice = prices[i];
                frontProfit[i] = frontProfit[i-1];
            }
        }
    
        // calculate the max profit using 1 (or fewer) transaction between day i (variable) thru last day
        // store the results in another array
        buyPrice = prices[prices.length - 1];
        maxDiff = 0;
        backProfit[prices.length-1] = 0;
    
        for(var i = prices.length - 2; i >= 0; i--) {
            backProfit[i] = backProfit[i+1];
            var diff = buyPrice - prices[i]; // note the order is different
            // next price is higher (by at least maxDiff), then update sellPrice
            if(diff > maxDiff) {
                maxDiff = diff;
                sellPrice = prices[i];
                backProfit[i] = maxDiff;
            }
            // next price is lower : decreasing interval
            if(diff < 0) {
                buyPrice = prices[i];
                backProfit[i] = backProfit[i+1];
            }
        }
        
        
        for(var j = 0; j < prices.length; j++) {
            maxProfit = Math.max((frontProfit[j] + backProfit[j]), maxProfit);
        }
        
        return maxProfit;
        
    };
    
    /*
    var calc = function(arr, start, end) {
        // end is excluded
        var prices = arr.slice(start, end);
        if(prices.length < 2) {
            return 0;
        }
        
        var buyPrice = Number.MAX_VALUE;
        var maxDiff = -1;
        var sellPrice;
        
        // buy low, sell high
        for(var i = 0; i < prices.length; i++) {
            var diff = prices[i] - buyPrice;
            // next price is higher (by at least maxDiff), then update sellPrice
            if(diff > maxDiff) {
                maxDiff = diff;
                sellPrice = prices[i];
            }
            // next price is lower : decreasing interval
            if(diff < 0) {
                buyPrice = prices[i];
            }
        }
        
        if(maxDiff > -1) {
            return maxDiff;
        } else {
            return 0;
        }
    }
    */
    

Log in to reply
 

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