Just Share My Simple Java AC Code


  • 0
    H
    public int maxProfit(int[] prices) {
        if(null == prices || prices.length <= 1) return 0;
        int maxProfit = 0;
        //max profit from first day to day i
        int[] left2Right = new int[prices.length];
        //min profit form last day to day i
        //suppose you can buy stock on day i and sell it on day i-k
        int[] right2Left = new int[prices.length];
        int preMin = prices[0];
        int curMax = 0;
        for(int i=0;i<prices.length;i++) {
            left2Right[i] = Math.max(curMax, prices[i] - preMin);
            curMax = left2Right[i];
            if(prices[i] < preMin) preMin = prices[i];
        }
        int preMax = prices[prices.length-1];
        int curMin = 0;
        for(int i=prices.length-1;i>=0;i--) {
            right2Left[i] = Math.min(curMin, prices[i]-preMax);
            curMin = right2Left[i];
            if(prices[i] > preMax) preMax = prices[i];
        }
        
        maxProfit = 0;
        for(int i=0;i<prices.length;i++) {
            if(left2Right[i] - right2Left[i] > maxProfit) {
                maxProfit = left2Right[i] - right2Left[i];
            }
        }
        return maxProfit;
    }

Log in to reply
 

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