Easy to understand solution in java with explaination for beginners.


  • 1
    public class Solution {
    //Compute the max profit we can get start from day 0  to day " i " with no more than one transaction(one buy and one sell), save the result in int[] front;
        public static void computeFront(int[] prices, int[] front)
    	{
    		int bought = prices[0];
    		int max = 0;
    		for(int i = 0; i < prices.length;i++)
    		{
    			if(prices[i] > bought)
    			{
    				max = Math.max(max,prices[i] - bought);
    			}
    			else
    				bought = prices[i];
    			front[i] = max;
    		}
    	}
    //Compute the max profit we can get start from day " i " to the end with no more than one transaction(one buy and one sell) ,save the result in int[] back;
    	public static void computeBack(int[] prices, int[] back)
    	{
    		int sell = prices[prices.length - 1];
    		int max = 0;
    		
    		for(int i = prices.length - 2; i >= 0;i--)
    		{
    			if(prices[i] < sell)
    			{
    				max = Math.max(max, sell - prices[i]);
    			}
    			else
    				sell = prices[i];
    			back[i] = max;
    		}
    	}
        public static int maxProfit(int[] prices) {
            
            if(prices == null || prices.length < 2)
                return 0;
            int len = prices.length;
            int maxProfit = 0;
    		int[] front = new int[len];
    		int[] back = new int[len];
    		computeFront(prices,front);
    		computeBack(prices,back);
    		for(int i = 1 ; i < len ;i++)
    		{
    //Split the whole process into two parts start from day 0, and find the largest combination of the two parts;
    			maxProfit = Math.max(maxProfit, front[i]+back[i]);
    		}
    		
    		return maxProfit;
    		
        }
    }

Log in to reply
 

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