30.连续子数组的最大和

题目描述：

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof

知识点：

• 动态规划

解题思路：

• 这道题给我们一个有负数的数组，要求我们求其连续的子数组最大的和，我们可以先想一下如果给我们一个数组要求我们求其累加和该怎么求
• 我们会遍历整个数组，让nums[i] = nums[i-1] + nums[i]，这样数组的最后一个元素就是所有元素的累加和了
• 那么对于这道题来说，我们要求其最大的累加和只需要去掉为负的子数组便好了，Math.max(0,nums[i-1])
• 我们初始默认第0位是最小的，最后我们让第i位与我们最大值相比较，更新我们的最大值便好

解题代码：

function FindGreatestSumOfSubArray(array)
{
    // write code here
    let max = array[0];
    for(let i = 1;i<array.length;i++) {
        array[i] = Math.max(0,array[i - 1]) + array[i];
        if(array[i] > max) max = array[i];
    }
    return max;
}