连续子数组的最大和

题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)

这道题目可以分解为一个相同的模式：

假设有一个数组int[] array = {1, -2, 3, 10, -4, 7, 2, -5}，那么：

前1个数的最大和：只有一个数，明显为1，

前2个数的最大和：看第二个数加上前1个数是变大还是变小，即分析前1个数的最大和为正还是为负，若为负，则最大和为array[1], 否则为前1个数最大和加上array[1]。

前3个数的最大和：分析前2个数的最大和为正还是负，若为负，则最大和为array[2]，否则为前2个数最大和加上array[2]。

……

……

最后很容易得到前n个数的最大和。

[table id=4 /]

public class Solution {
    public static int FindGreatestSumOfSubArray(int[] array) {
        //切勿忘记考虑健壮性
        if (array.length==0 || array==null) {
            return 0;
        }
        int sum = 0, Max = Integer.MIN_VALUE;
        for(int i = 0; i < array.length; i++) {
            if(sum <= 0)
                sum = array[i];
            else
                sum += array[i];
            if(sum > Max) 
                Max = sum;
        }
        return Max;
    }
}