题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
分析
首先如果数组里面全是小于0的负数，那么连续数组的最大和就是那个最大的负数
如果里面有正数还有负数，那么从左开始累加，如果遇到累加和小于0，则说明这一段数组不会是构成最大和的连续子数组，道理很简单，如果构成最大和的连续子数组中包含这么一段累加和为负数的子数组，那么去掉它们之后和不就更大了么？所以不会包含。
需要两个变量max和cur，cur记录当前的累积和，小于0立马开始从0计算，max记录遍历过程中出现过的累积和中的最大值。
代码实现
function FindGreatestSumOfSubArray(arr) { if(arr.length === 0) return; if(arr.length === 1) return arr[0]; var allNeg = true; var negMax = -Infinity; for(var i = 0;i < arr.length;i++) { if(arr[i] > negMax){ negMax = arr[i]; } if(arr[i] >= 0){ allNeg = false; } } if(allNeg) return negMax; var max = -Infinity, cur = 0; for(var i = 0;i < arr.length;i++) { cur += arr[i]; max = Math.max(max, cur); cur = cur >=0 ? cur : 0; } return max; }
