My easy understanding DP solution with brief explaination,O(n) time and O(n) space


  • 0
    D
    public class Solution {
    public int maxProfit(int[] prices) {
           if(prices.length==0 ) return 0;
    	        int[] front=new int[prices.length];
    	        int[] back=new int[prices.length];
    	        int min=prices[0];
    	        int max=prices[prices.length-1];
    	        front[0]=0;
    	        back[prices.length-1]=0;
    	        //front[i] store the maxium profile from start to node i;
    	         for(int i=1;i<prices.length;i++){
    	          min=Math.min(min,prices[i]);
    	          front[i]=prices[i]-min>front[i-1]?prices[i]-min:front[i-1];
    	         }
    	         //back[i] store the -maxium(negative) profile from node i to end;
    	         for(int i=prices.length-2;i>=0;i--){
    		          max=Math.max(max,prices[i]);
    		          back[i]=prices[i]-max<back[i+1]?prices[i]-max:back[i+1];
    		         }
    	         
    	         int res=0;
    	         //use one iteration to find maxium profile
    	         for(int i=0;i<prices.length;i++){
    	        	 res=Math.max(res,front[i]-back[i]);
    	        	 
    	        	 
    	         }
    	         
    	         return res;
    	    }}

Log in to reply
 

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