Javascript DP solution that beats 100%!


  • 2
    C

    profit[i] is the maximum profit one can obtain doing one transaction given prices[0..i].

    profit2[i] is the maximum profit one can obtain doing one transaction given prices[i..n-1].

    var maxProfit = function(prices) {
        if (prices.length === 0) return 0;
        
        var min = prices[0];
        var max = prices[0];
        var profits = [ 0 ];
        var profits2 = [ 0 ];
        var profit = 0;
        var cur, i;
        
        // from left to right.
        for (i = 1; i < prices.length; ++i) {
            cur = prices[i];
            
            if (cur > max) {
                max = cur;
                if (max - min > profit) profit = max - min;
            }
            if (cur < min) {
                min = cur;
                max = cur;
            }
    
            profits[i] = profit;
        }
        
        min = prices[prices.length - 1];
        max = prices[prices.length - 1];
        profit = 0;
        
        // from right to left.
        for (i = prices.length - 2; i >= 0; --i) {
            cur = prices[i];
            
            if (cur < min) {
                min = cur;
                if (max - min > profit) profit = max - min;
            } else if (cur > max) {
                max = cur;
                min = cur;
            }
            
            profits2[i] = profit;
        }
        
        // find the max of (profits[i] + profits2[i]).
        max = 0;
        for (var j = 0; j < profits.length; ++j) {
            profit = profits[j] + profits2[j];
            if (profit > max) {
                max = profit;
            }
        }
        
        return max;
    };

  • 0
    B

    would your solution not simply return 2 times the max sell/buy combo?


  • 0
    C

    No, it won't. The two scan computes the different things.


  • 0
    B

    Yes, that's right. I was able to understand the intuition. For others that come by this solution, the way it works is: The forward pass places at each time point the maximum amount of money one could have made with one buy/sell up to that point, and the backwards pass places at each time point the maximum amount of money one could have made with one buy/sell after that point.

    Thus, in the final loop calculation, you check each time point for the sum of what could be the max profit before and after it. The max of these is the maximum amount you could have made with this stock price series.


Log in to reply
 

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