question: public static int maxProfit ( int [ ] prices ) { if ( prices == null || prices . length < 2 ) { return 0 ; } int max = 0 ; int min = prices [ 0 ] ; for ( int i = 1 ; i < prices . length ; i ++ ) { min = Math . min ( min , prices [ i ] ) ; if ( prices [ i ] > prices [ i - 1 ] ) { max = Math . max ( max , prices [ i ] - min ) ; } } return max ; }
target:  Optimized bottom-up approach O(n) Time, O(1) Space Just record yesterday's profit Update min, max and profit If next price is bigger, it's only possible to update the profit If next price is smaller or equal, it's only possible to update min