刷题22——面试题42：连续子数组的最大和

题目：

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

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

最直观的解法，即枚举数组的所有子数组并求出它们的和。一个长度为n的数组，总共有n(n+1)/2个子数组。计算出所有子数组的和，最快也需要O(n2)时间。

思路一：举例分析数组的规律

我们试着从头到尾逐个累加示例数组中的每个数字。初始化和为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

思路二：应用动态规划法

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

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

python代码如下：

def FindGreatestSumOfSub(nums):
    if not nums:
        return 0
    
    sum =0
    res =nums[0]
    for i in range(len(nums)):
        if sum <=0:
            sum =nums[i]
        else:
            sum +=nums[i]
            
        if sum >res:
            res =sum
            
    return res

刷题22——面试题42：连续子数组的最大和