My jave accepted solution with O(N) time and O(1) space


  • 52
    S

    The idea is to find so far min price.

     public int maxProfit(int[] prices) {
    		 if (prices.length == 0) {
    			 return 0 ;
    		 }		
    		 int max = 0 ;
    		 int sofarMin = prices[0] ;
    	     for (int i = 0 ; i < prices.length ; ++i) {
    	    	 if (prices[i] > sofarMin) {
    	    		 max = Math.max(max, prices[i] - sofarMin) ;
    	    	 } else{
    	    		sofarMin = prices[i];  
    	    	 }
    	     }	     
    	    return  max ;
    	 }

  • 1
    R

    I prefer this solution rather than differ array and convert it to max sub array sum problem, as this is more understanding and easy coding


  • -18
    J

    This is understandable, but not really available in market.

    The price in the future is not predictable. you buy it, you have it, you are not able to buy in a lower price tomorrow.


  • 0
    C

    @ruichang I think so!


  • 0
    L

    Very straight forward solution! Thank you!


Log in to reply
 

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