Kadane's Algorithm

关于该种算法的两个例子：

例一：
给定一个数组array，返回子数组的最大累加和。
举例：array=【1，-2，3，5，-2，6，-1】，所有的子数组中【3，5，-2，6】可以累加出最大的和12，返回12.

public class MaxSubarray {

    public int maxSubarray(int[] array) {
        int max = 0;
        int cur = 0;
        for(int i = 0; i < array.length; i++) {
            cur += cur + array[i];
            max = Math.max(cur, max);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }

}

只需要遍历一遍。思路：比如 arr[ i ] +.......+ arr[ j ] < 0， 刚好到 j 处小于0，这代表从 arr[ i + 1 ]开始加到 j 处都小于0，即可以跳过这这一段从 j + 1 处开始（并不是说最大子数组不再这里）。

例二：
Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

这是LeetCode的121题：

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

思路：将数组分块来看，分块标准：比如块【i, i+1.......j】，从arr[ i+1 ]到 arr[ j ] 都大于arr[ i ]，arr[ j+1 ]一定小于或等于arr[ i ]，这样接下来只要从j+1处开始，重复上述操作。

总结：Kadane's Algorithm在我看来就是将数组按一定规则分块来看，用这种思维来思考问题。