最大子数列问题 - LC121 Best Time to Buy

这个问题实际上是 Kadane's Algorithm 算法问题，但我觉得也可以理解为两个常量的动态比较问题。

我的实现方法如下

    public int maxProfit(int[] prices) {
        if(prices.length < 2) return 0;
        int purchasePrice = prices[0];
        int profit = 0;
        for(int i = 1; i< prices.length; ++i){
            //确定每次比较新价格的时候拿到profit是最大的
            profit = Integer.max(profit, prices[i] - purchasePrice); 
            //确定每次比较新价格的时候买入价是最小的(即找到小的数字就不会再管前面的数字了，因为前面的最大利益以及算出来的)
            purchasePrice = Integer.min(purchasePrice, prices[i]); 
        }
        return profit;
    }

正规实现方法如下

    public int maxProfit(int[] prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }

Java8 的简化写法

int min = Integer.MAX_VALUE;
public int maxProfit(int[] prices) {
    return Arrays.stream(prices).map(i -> i - (min = Math.min(min, i))).max().orElse(0);
}

参考
https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98