Best Time to Buy and Sell Stock I & II

啊 第一次直接过small和big测试 好爽！虽然主要是以前知道这个题目吧= =
以前一直想不清这个题目的算法，今天终于搞明白了。思路很简单：就是用i遍历第2到最后一天，看第i天卖最大的profit是多少。当然，这就需要维护一个前i项最小值的变量，很简单啦。这里还有一个问题，就是如果最大profit都小于0，那不如不卖。就像期货界里大家说的那样，你不交易，就已经超越80%的人了 = =
恩 代码就是这样。。。

public class Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int length = prices.length;
        int max;
        if (length > 1)
            max = prices[1] - prices[0];
        else
            max = 0;
        if (max < 0) 
            max = 0;
        int min = (length > 0 ? prices[0]: 0);
        for (int i = 1; i < length; ++i){
            if (prices[i] < min){
                min = prices[i];
                continue;
            }
            if (prices[i] - min > max)
                max = prices[i] - min;
        }
        return max;
    }
}

然后手痒做了后面的II，发现概念有点类似于<modeling maximum profit with C++>这本书里的potential profit概念，只是<modeling>这本书里可以卖空，这道题只可以买进而已
思路应该比较简单，识别所有的上升波段即可。

public class Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int trend = 0;
        int length = prices.length;
        if (length < 2)
            return 0;
        int min = prices[0];
        int profit = 0;
        for (int i = 1; i < length - 1; ++i){
            if (prices[i] > prices[i-1]){
                if (trend != 1){
                    trend = 1;
                    min = prices[i-1];
                }
            } else{
                if (trend == 1){
                    profit += prices[i-1] - min;
                    trend = -1;
                }
            }
        }
        if (prices[length-1] > prices[length-2]){
            if (trend != 1)
                profit += prices[length-1] - prices[length-2];
            else
                profit += prices[length-1] - min;
        } else if (trend == 1)
                profit += prices[length-2] - min;
        
        return profit;
    }
}

囧 写了好几次都没过= = 主要原因是最后一天结束的时候，如果是上涨的话，按照原来算法就会不管，继续等以后的交易，可是以后就没有交易了，这样只能把最后一天单独拿出来考虑。囧，单独考虑的时候又出了一些错误，唉唉唉，还是太弱了