题目

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

方法

方法：动态规划思想
参考：https://blog.csdn.net/qq_34528297/article/details/72700695
时间复杂度：O(n)

思路

题目的难点在数组元素可能为负数，负数在子序列和中呈现“减小”的效果。可以借用动态规划的思路，当求某个元素为结尾的子序列最大和的时候，存在两种情况，一种是从前面该元素前的子序列最大和累加过来；另一种是，如果该元素前的子序列和是负数，那么该元素为结尾的子序列最大和，就不必从前面元素累计了，直接取该元素即可。
结合具体例子看：{1 ， -2 ， 3 ， 10 ， -4 ， 7 ， 2 ， -5 }
在遍历这个数组时，从第一个开始，累加sum为1，到-2，累加为-1，再到3，发现如果子序列是1、-2、3，sum为2，比3本身还小。所以3结尾的子序列最大和，直接取3即可。然后舍弃前面的累加，继续往下遍历。到10，sum为13，目前位置13是最大的子序列和。到-4，累加值变小，为9。到7，累加值变为16，比之前的13还大，所以最大子序列变为16。到2，sum为18。最后的-5，不加入子序列最大和的序列里

具体方法

从上面的例子中，可以看出，再遍历过程中，需要保存前面出现的最大子序列和sum，和当前累加值。如果遍历碰到正数，累加值会一直增加，那么当前的最大子序列和sum也会一直增加；如果碰到负数，累加值减少，sum暂时不变，因为一开始就提到了，负数对于序列和呈现“减小”的效果。直到如果又碰到正数，将累加值重新增加，直到增加到比刚才的子序列最大和sum还大的时候，sum就替换新值；但如果累加值一直减小到负数，那么就借鉴上述的动态规划思想，累加值直接去遍历的下一个新值即可。
遍历结束后，sum就是子序列最大和

代码

function FindGreatestSumOfSubArray (array) {
  // write code here
  let sum = Number.MIN_SAFE_INTEGER
  let current = 0
  array.forEach((item, index) => {
    if (current < 0) {
      current = 0
    }
    current += item
    if (current > sum) {
      sum = current
    }
  })
  return sum
}