Java solution in O(n)


  • 0
    L

    This problem has one of the most submissions so apparently it is one of the most popular questions. Nonetheless, the obvious n^2 solution is of no use since that is not expected for this problem. The simple Java solution should work in O(n).

    public int maxProfit(int[] prices) {
            if(prices.length==0) {
                return 0;
            }
            int min=prices[0];
            int maxprofit=0;
            for(int i=0;i<prices.length;i++) {
                maxprofit = Math.max(maxprofit,prices[i]-min);
                min =  Math.min(min,prices[i]);
            }
            
            return maxprofit;        
        }
    

Log in to reply
 

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