Java Solution (1ms) in O(3*n) time, O(2*n) space, using min and max arrays


  • 0
    A

    I took a slightly different approach to this (maybe I overthought it, oh well). My intuition was, the max profit at any point is going to be the difference between the minimum value before that point and the maximum value after that point.

    Basically, I scan the prices in increasing order and create an array that keeps track of the minimum value seen so far (so mins[i] is the minimum value of prices from 0 to i). I do the same thing for the maximum values, but in decreasing order. Then I iterate through both arrays, finding the greatest difference, which is the max profit.

    public int maxProfit(int[] prices) {
        int[] mins = new int[prices.length];
        int[] maxes = new int[prices.length];
        int currMin = Integer.MAX_VALUE;
        int currMax = 0;
        for(int i = 0; i < prices.length; i++) {
            currMin = Math.min(currMin, prices[i]);
            mins[i] = currMin;
        }
        for(int i = prices.length-1; i >= 0; i--) {
            currMax = Math.max(currMax, prices[i]);
            maxes[i] = currMax;
        }
        int maxProfit = 0;
        for(int i = 0; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, maxes[i] - mins[i]);
        }
        return maxProfit;
    }

Log in to reply
 

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