连续子数组的最大和

题目：

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

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

分析与解法

解法一：举例分析数组的规律

我们试着从头到尾逐个累加示例数组中的每个数字。初始化和为 0。第一步加上第一个数字 1， 此时和为 1。接下来第二步加上数字 -2，和就变成了 -1。第三步刷上数字3。我们注意到由于此前累计的和是 －1 ，小于 0，那如果用-1 加上 3 ，得到的和是 2 ， 比 3 本身还小。也就是说从第一个数字开始的子数组的和会小于从第三个数字开始的子数组的和。因此我们不用考虑从第一个数字开始的子数组，之前累计的和也被抛弃。

我们从第三个数字重新开始累加，此时得到的和是 3。接下来第四步加 10，得到和为 13 。第五步加上 -4， 和为 9。我们发现由于 -4 是一个负数，因此累加 -4 之后得到的和比原来的和还要小。因此我们要把之前得到的和 13 保存下来，它有可能是最大的子数组的和。第六步加上数字 7，9 加 7 的结果是 16，此时和比之前最大的和 13 还要大， 把最大的子数组的和由 13 更新为 16。第七步加上 2，累加得到的和为 18，同时我们也要更新最大子数组的和。第八步加上最后一个数字 -5，由于得到的和为 13 ，小于此前最大的和 18，因此最终最大的子数组的和为 18 ，对应的子数组是｛3, 10, -4, 7, 2｝。

步骤	操作	累加的子数组和	最大的子数组和
1	加 1	1	1
2	加 -2	-1	1
3	抛弃前面的和 -1，加 3	3	3
4	加 10	13	13
5	加 -4	9	13
6	加 7	16	16
7	加 2	18	18
8	加 -5	13	18

参考代码如下：

class Solution {

    public static int getMaxSum(int[] nums, int length) {
        if (null == nums || length <= 0) {
            return 0;
        }

        int currSum = 0;
        int maxSum = nums[0]; // 全负情况，返回最大数

        for (int j = 0; j < length; j++) {
            currSum = Math.max(nums[j], currSum + nums[j]);
            maxSum = Math.max(maxSum, currSum);
        }

        return maxSum;
    }
}

解法二： 应用动态归划法。

可以用动态规划的思想来分析这个问题。如果用函数 f(i)表示以第 i 个数字结尾的子数组的最大和，那么我们需要求出 max[f(i)]，其中 0 <= i < n。我们可用如下边归公式求 f(i):

这个公式的意义：当以第 i-1 个数字结尾的子数组中所有数字的和小于 0 时，如果把这个负数与第 i 个数累加，得到的结果比第 i 个数字本身还要小，所以这种情况下以第 i 个数字结尾的子数组就是第 i 个数字本身。如果以第 i-1 个数字结尾的子数组中所有数字的和大于 0，与第 i 个数字累加就得到以第 i 个数字结尾的子数组中所有数字的和。

​ 虽然通常我们都会用递归的方式解析动态规划的问题，但最终都会基于循环去编码。上述公式对应的代码和前面给出的代码一致。递归公式中的 f(i) 对应的变量是 currSum，而 max[f(i)] 就是 maxSum。因此，可以所这两种思路是异曲同工的。

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md