Java simple solution with explanation


  • 1
    H

    Since we are allowed for only one transaction(buy 1 time, and sell 1 time), we need to find the largest increasing interval within the entire time period to maximize the profit.

    basic idea: the maximal increasing interval until Day N will always be the larger one between the maximal increasing interval until Day N-1 or Day N's price - the lowest price before Day N.

    public int maxProfit(int[] prices) {
        if(prices.length==0 || prices.length==1) return 0;
        
        int result = 0;
        int lowestPrice = prices[0];
        int maxInterval = 0;
        
        for(int i=1; i<prices.length; i++){
            int dif = prices[i]-lowestPrice;
            maxInterval = Math.max(dif, maxInterval);
            lowestPrice = Math.min(lowestPrice, prices[i]);
        }
        
        return maxInterval;
    }

Log in to reply
 

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