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


  • 54
    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!


  • 0
    R

    really love this solution, directly compare with minimum value rather than the previous value!


  • 0
    Y

    Definitely, I have a solution withO(logn)time, using recursion to get min, max and maxprofit from left part and right part each time.


Log in to reply
 

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