O(n) java solution using one forward and one backward buy stock I solution and merge up.


  • 0
    L
    public class Solution {
        public int maxProfit(int[] prices) {
            if(prices.length<=1) return 0;
            int[] oneTran = new int[prices.length];
            int preMin = prices[0];
            for(int i= 1;i<prices.length;i++){
            	oneTran[i] = (oneTran[i-1]>prices[i]-preMin)?oneTran[i-1]:(prices[i]-preMin);
            	preMin = preMin<prices[i]?preMin:prices[i];
            }
            int[] oneTranBackward = new int[prices.length];
            int preMax = prices[prices.length-1];
            for(int i= prices.length-2;i>=0;i--){
            	oneTranBackward[i] = (oneTranBackward[i+1]>preMax-prices[i])?oneTranBackward[i+1]:preMax-prices[i];
            	preMax = preMax>prices[i]?preMax:prices[i];
            }
            int maxProfit = oneTran[oneTran.length-1];
            for(int i=0;i<oneTran.length-1;i++){
                if(maxProfit<oneTran[i]+oneTranBackward[i+1]) maxProfit = oneTran[i]+oneTranBackward[i+1];
            }
            return maxProfit;
        }
    }

Log in to reply
 

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