BiruLyu
6/20/2017 - 7:43 AM

121. Best Time to Buy and Sell Stock.java

public class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        if (prices == null || prices.length <= 1) return res;
        int minSoFar = prices[0];
        for (int price : prices) {
            minSoFar = Math.min(minSoFar, price);
            res = Math.max (res, price - minSoFar);
        }
        return res;
    }
}

// OPT[i] = max(0, OPT[i - 1] + nums[i] - nums[i - 1]);