[leetcode] #121 Best Time to Buy and Sell Stock

這題是給一個 stock price array,  要求一買一賣（＊僅能先買後賣）後的最大獲益。
這題很類似 longest subsequence of Integer array, 不過僅只要記錄兩個elements 差的最大值。

   profit = maximum(-BuyPrice + SellPrice )

step 1.  profit =  [ prices[i] - minimum( prices[:i-1]) if prices[i] - minimum( prices[:i-1]) > profit ][0]
step 2. minimum( prices[:i-1] 可拆解為 minPrice = price[0]; ...  minPrice = min(minPrice, price[i]);

1:    public int maxProfit(int[] prices) {  
2:      if (prices.length <= 1) {  
3:        return 0;  
4:      }  
5:      int profit = 0;  
6:      int minPrice = prices[0];  
7:      for (int i=1;i<prices.length;i++) {  
8:        if (prices[i] - minPrice > profit) {  
9:          profit = prices[i] - minPrice;  
10:        }  
11:        if (minPrice > prices[i]) {  
12:          minPrice = prices[i];  
13:        }  
14:      }  
15:      return profit;  
16:    }