连续子数组的最大和（java）

题目描述：

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

分析：

最开始理解错了，以为是从头开始，后面得到的和最大，这种情况用一个hashmap存贮每一步得到的sum即可，然后拿出最大的即可。

后面发现原来不是一定从头开始，要让连续子向量最大的和的片段。也就是说开头不固定，结尾也不固定。

沿用累加的思路。
显然，一个数字加上任意一个正数是比它自己要大的。
题目中要求连续自向量的和最大，那么我们就考虑从第一位开始求和，当和小于0时，则从下一个开始重新求和；当和大于0时，继续求和，并用一个变量记录加上下一个之前的和值，判断继续的加法是否让结果变小了，用这个变量记录两者之间的较大值。

解答：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0 || (array.length == 1 && array[0] <= 0)) return 0;
        int sum = array[0];  //累加求和
        int max = array[0];  //记录最大值
        for (int i = 1; i < array.length; i++) {
            sum = (sum > 0) ? (sum + array[i]) : array[i];
            max = Math.max(max, sum);
        }
        return max;
    }
}

运行结果