最大子陣列
重要性：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該演算法精確需要 1 次陣列遍歷，因此時間複雜度為 O(n)。
您可以在此處找到有關該演算法的更詳細資訊：最大子陣列問題。如果仍然不明白為什麼這樣做有效，請根據上述範例追蹤演算法，瞭解其運作方式，這比任何文字都更好。