*(6/1/16)Leetcode 121. Best Time

One pass, bug free: 10分钟
1.一切从简单考虑:两种情况，升，降都覆盖到。

public class Solution {
    public int maxProfit(int[] prices) {
        //8:45
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int profit = 0, max_profit = 0;
        int length = prices.length;
        for (int i = 0; i < length; i++){
            if(prices[i] < min){
                min = prices[i];
                max = prices[i];
                profit = max - min;
            }
            else if(prices[i] > max){
                max = prices[i];
                profit = max - min;
            }
            max_profit = Math.max(max_profit, profit);
        }
        return max_profit;
    }
}

解法二:
以上解法并不好，没有体现DP的思想不利于扩展
DP解法: time:O(n); Space:O(n)

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int length = prices.length;
        int[] left = new int[length];
        int min = prices[0];
        for(int i = 1; i<length; i++){
            min = Math.min(min, prices[i]);
            left[i] = Math.max(left[i-1], prices[i] - min);
        }
        return left[length-1];
    }
}

解法三:
将解法二Space降为O(1):

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int length = prices.length;
        int left = 0;
        int min = prices[0];
        for(int i = 1; i<length; i++){
            min = Math.min(min, prices[i]);
            left = Math.max(left, prices[i] - min);
        }
        return left;
    }
}