有一個函式可以找到子陣列中最大的和
var maxSubArray = function(nums) {
if(nums.length == 0) return 0;
let result = Number.MIN_SAFE_INTEGER;
let sum = 0;
for(let i = 0; i < nums.length; i ) {
sum = nums[i];
result = Math.max(sum, result);
sum = sum < 0 ? 0 : sum;
}
return result;
};
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]));
但我無法理解發生了什么變化以及為什么洗掉以下行會停止作業：'result = Math.max(sum, result);'
并將回傳結果更改為 sum
uj5u.com熱心網友回復：
如果您對結果行進行注釋，則該函式基本上不會有先前“最佳總和的候選者”的記憶。它只會遍歷陣列，向sum變數添加值，即使它降低了總和的值（這是無法避免的，只有在跟蹤之前的最佳總和候選時才有用）。
為了進一步解釋，假設您注釋該行并回傳sum。每次總和結果為負時，它將立即重置為 0。因此，在您提出的示例中，最終的最大子陣列將有效地開始4求和，如果總和sum大于零，即使在添加后也將繼續求和總和小于其先前值的新值。
所以基本上它會是這樣的：
[-2] // sum = -2. Less than 0, so reset to sum = 0
[-2, 1] // sum = 1
[-2, 1, -3] // sum = -2. Less than 0, so reset to sum = 0
[-2, 1, -3, 4] // sum = 4
[-2, 1, -3, 4, -1] // sum = 3
[-2, 1, -3, 4, -1, 2] // sum = 5
[-2, 1, -3, 4, -1, 2, 1] // sum = 6 BEST SUM
[-2, 1, -3, 4, -1, 2, 1, -5] // sum = 1 :(
[-2, 1, -3, 4, -1, 2, 1, -5, 4] // sum = 5
這就是為什么變數result是必要的。可以這么說，您必須跟蹤迄今為止的最佳總和并將其與“本地最佳”進行比較。
在原始代碼中，整個迭代程序中的狀態如下所示：
[-2]
// sum = -2
// result = -2 because -2 is greater than Number.MIN_SAFE_INTEGER.
// sum = 0. It gets reset because it's negative
[-2, 1]
// sum = 1
// result = 1 because 1 > -2
[-2, 1, -3]
// sum = -2
// result = 1 and isn't updated because the overall max sum so far is greater than the current sum
// sum = 0
[-2, 1, -3, 4]
// sum = 4
// result = 4
[-2, 1, -3, 4, -1]
// sum = 3
// result = 4 and isn't updated because the overall max sum is greater than the current sum
[-2, 1, -3, 4, -1, 2]
// sum = 5
// result = 5
[-2, 1, -3, 4, -1, 2, 1]
// sum = 6 BEST SUM
// result = 6
[-2, 1, -3, 4, -1, 2, 1, -5]
// sum = 1
// result = 6
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
// sum = 5
// result = 6
如您所見，最終值現在是 6，因為總體最大總和保留在result變數中，同時sum跟蹤區域最佳值。
uj5u.com熱心網友回復：
這是Kadane's Algorithmfor的實作Largest Sum Subarray。
演算法的要點是：
不要添加已經總結為負數的子陣列。這只會進一步減少總和。
結果必須每次更新，子陣列的總和的值大于當前值
例如：這是在相關位置添加console.log的輸出。
Note: Here is the link where you can read more: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
uj5u.com熱心網友回復：
它是將所有相鄰元素相加以獲得最大和的子陣列。
在上面的例子中，子陣列是 [4,-1,2,1]
總和小于 6 的所有其他子陣列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/364987.html
標籤：javascript