最大子数组
重要性: 2
输入是一个数字数组，例如 arr = [1, -2, 3, 4, -9, 6]。
任务是：找到 arr 中具有最大项目总和的连续子数组。
编写函数 getMaxSubSum(arr)，它将返回该总和。
例如
getMaxSubSum([-1, 2, 3, -9]) == 5 (the sum of highlighted items)
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6 (take all)如果所有项目都是负数，则意味着我们不取任何项目（子数组为空），因此总和为零
getMaxSubSum([-1, -2, -3]) = 0请尝试想出一个快速解决方案：O(n2) 甚至 O(n) 如果可以。
慢速解决方案
我们可以计算所有可能的子总和。
最简单的方法是取每个元素并计算从该元素开始的所有子数组的总和。
例如，对于 [-1, 2, 3, -9, 11]
// Starting from -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11
// Starting from 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11
// Starting from 3:
3
3 + (-9)
3 + (-9) + 11
// Starting from -9
-9
-9 + 11
// Starting from 11
11代码实际上是一个嵌套循环：外部循环遍历数组元素，内部循环计算从当前元素开始的子总和。
function getMaxSubSum(arr) {
let maxSum = 0; // if we take no elements, zero will be returned
for (let i = 0; i < arr.length; i++) {
let sumFixedStart = 0;
for (let j = i; j < arr.length; j++) {
sumFixedStart += arr[j];
maxSum = Math.max(maxSum, sumFixedStart);
}
}
return maxSum;
}
alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100该解决方案的时间复杂度为 O(n2)。换句话说，如果我们将数组大小增加 2 倍，算法将运行时间延长 4 倍。
对于大型数组（1000、10000 或更多项），此类算法会导致严重的迟缓。
快速解决方案
让我们遍历数组并将当前元素的偏总和保存在变量 s 中。如果 s 在某个时刻变为负数，则将 s=0。所有此类 s 的最大值将是答案。
如果描述过于模糊，请查看代码，它足够短
function getMaxSubSum(arr) {
let maxSum = 0;
let partialSum = 0;
for (let item of arr) { // for each item of arr
partialSum += item; // add it to partialSum
maxSum = Math.max(maxSum, partialSum); // remember the maximum
if (partialSum < 0) partialSum = 0; // zero if negative
}
return maxSum;
}
alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0该算法只需要遍历数组一次，因此时间复杂度为 O(n)。
您可以在此处找到有关该算法的更多详细信息：最大子数组问题。如果仍然不清楚为什么它有效，请在上面的示例中跟踪该算法，看看它是如何工作的，这比任何文字都更好。