剑指offer[30]——连续子数组的最大和

题目描述

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

这道题目属于动态规划的题目，要注意题目中说的最大连续子序列不一定是从0开始的。我们新建两个变量res与max，其中res是用来存储连续子序列的和加到第n位时的最大值，比如

[[6,-3,-2,7,-15,1,2,2] ]

该数组第三位7的最大值为8；max顾名思义就是用来存储连续子序列最大值的，我们将其初始化为数组的第一个数，按照上述序列来的话就是初始化为6。

我们还是按照上述序列举例，从第一位-3开始遍历，我们首先用res[0]加-3的出来的结果是3，显然比-3大，那我们就令res[1]等于3，从第一位一直到第四位都是一样的，我们来分析一下第五位1，我们用res[4]加1的出来的是-6，显然比1小，那这个时候res[5]就应该赋值为1，因为后面的数字2加1就可以了，为什么要加一个比1小的数字呢，因为我们这里求的是最大值，所以保留最大值即可。

代码如下：

function FindGreatestSumOfSubArray(array)
{
    let res = [array[0]];
    let max = array[0];
    const _length = array.length;
    for(let i=1; i<_length; i++){
        let plus = array[i]+res[i-1];
        if(plus>array[i]){
            res.push(plus);
        }else{
            res.push(array[i]);
        }
        max = max>res[i]?max:res[i];
    }
    return max;
}