【分析数组的规律】30.连续子数组的最大和

题目

思路

初始化和为0，第一步，加上第一个数字1，此时和为1.，最大和也为1.接下来第二步加上-2，此时和为-1，最大和为1。第三步加上3，但是此时和为-1，而-1加3反而比3小，所以此时和应该直接变更为3，最大和也更新为3.接着加上10，和为13，最大和更新为13，然后加上-4，和为9，最大和不变仍为13，接着加上7和为16，最大和变为16……

综上所述，初始和为0，初始最大和为第一个元素，遍历数组求和时，每次循环都判断上一次的和是否小于等于零，若是，则直接把当前元素赋值给和；若不是，则直接加上当前元素。接着判断当前和是否大于最大和，若是，则将当前和赋值给最大和。

代码

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length <= 0)
            return 0;
        int sum = 0;
        //int greatestSum = 0x80000000;
        int greatestSum = array[0];
        for (int i = 0; i < array.length; i++) {
            if (sum <= 0)
                sum = array[i];
            else
                sum += array[i];
            if (sum > greatestSum)
                greatestSum = sum;
        }
        return greatestSum;
    }
}