连续子数组的最大和.md

note
createdAt modifiedAt tags id 2020-05-14 12:33:26 UTC 2020-05-15 10:25:56 UTC 考点/时间效率 难度/3

连续子数组的最大和

#考点/时间效率 #难度/3 牛客网

题目描述

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

答案

function FindGreatestSumOfSubArray(array) {
  if (array.length == 0) return 0;
  let temp = array[0],
    sum = array[0];
  for (let i = 1; i < array.length; i++) {
    temp = temp < 0 ? array[i] : temp + array[i];
    sum = sum > temp ? sum : temp;
  }
  return sum;
}