连续子数组的最大和

问题

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

代码实现

private static int FindGreatestSumOfSubArray(int[] array) {
    int max = array[0]; //保存最大和
    int sum = array[0]; //每次循环的数据和
    for (int i = 1; i < array.length; i++) {
        int cur = sum + array[i];
        sum = cur < array[i] ? array[i] : cur; //最主要的一行
        max = max < sum ? sum : max; //比较得出最大值
    }
    return max;
}

分析

刚开始还以为很简单，以为是从前往后求和，找出最大值。很快写出来但是傻眼了，不对！
看别人答案怎么那么离奇，不是很简单一道题吗，怎么写的这个逻辑。后来又想了下，才明白过来被忽悠了。子序列可以是数组中任何位置开始任何位置结束的一个数组！以下开始分析。

要做这道题，关键在于判断是否要加上当前元素。

例如输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为3, 10, -4, 7, 2。因此输出为该子数组的和18。

第一轮循环：1+ -2 = -1
想象现在有两个子序列：1前一个子序列到当前元素 2当前元素自己组成的子序列
现在要在两个子序列之间做取舍了
子序列1 {1 -2} 和为-1
子序列2 {-2} 和为-2
我们需要大的序列 也就是{1 -2}

第二轮循环：
子序列1 {1, -2, 3} 和为2
子序列2 {3} 和为3
子序列 1 < 2 所以现在要重置子序列为{3}

以此类推