求最大和子數(shù)組大小的 JavaScript 程序是編程領(lǐng)域中的一個(gè)常見問題，尤其是在 Web 開發(fā)中。問題陳述涉及在給定的一維整數(shù)數(shù)組中查找具有最大總和的連續(xù)子數(shù)組。這也稱為最大子數(shù)組問題。解決這個(gè)問題在各種應(yīng)用中都非常有用，例如財(cái)務(wù)分析、股票市場(chǎng)預(yù)測(cè)和信號(hào)處理。
在本文中，我們將看到算法以及使用 JavaScript 實(shí)現(xiàn)最大總和的子數(shù)組的大小。我們將首先詳細(xì)討論該問題，然后繼續(xù)使用 JavaScript 編程語(yǔ)言開發(fā)逐步解決方案。那么讓我們開始吧！
問題陳述
給定一個(gè)整數(shù)數(shù)組，我們必須找到具有最大總和的子數(shù)組的長(zhǎng)度。
例如，假設(shè)我們有一個(gè)整數(shù)數(shù)組：[1, -2, 1, 1, -2, 1]，最大子數(shù)組為 [1, 1]，總和為 2。我們可以通過用結(jié)束索引減去起始索引并加 1 來求出該子數(shù)組的長(zhǎng)度。在本例中，起始索引為 0，結(jié)束索引為 1，因此子數(shù)組的長(zhǎng)度為 2。
另一個(gè)例子是所有負(fù)整數(shù)的數(shù)組：[-2, -5, -8, -3, -1, -7]。在這種情況下，最大子數(shù)組將為 [-1]，總和為 -1。由于所有元素均為負(fù)數(shù)，因此絕對(duì)值最小的子數(shù)組的總和最大。因此，子數(shù)組的長(zhǎng)度為-1。
需要注意的是，可以有多個(gè)最大子數(shù)組，每個(gè)子數(shù)組的總和相同。然而，我們只需要找到其中之一。
算法
第 1 步
我們首先初始化四個(gè)變量：“maxSum”為“-Infinity”，“currentSum”為“0”，“start”為“0”，end 為“0”。我們將使用“maxSum”來跟蹤到目前為止我們看到的最大總和，“currentSum”來計(jì)算我們當(dāng)前迭代的子數(shù)組的總和，“start”來跟蹤子數(shù)組的起始索引，以及’end’ 來跟蹤子數(shù)組的結(jié)束索引。
第 2 步
然后我們使用“for”循環(huán)遍歷數(shù)組。對(duì)于數(shù)組中的每個(gè)元素，我們將其添加到“currentSum”中。如果 ‘currentSum’ 大于 ‘maxSum’，我們將 ‘maxSum’ 更新為 ‘currentSum’ 并將 ‘end’ 設(shè)置為當(dāng)前索引。
第 3 步
接下來，我們使用 while 循環(huán)來檢查“currentSum”是否小于“0”。如果是，我們從“currentSum”中減去“start”處的值，并將“start”加1。這確保了我們始終擁有數(shù)組的連續(xù)子集。
第 4 步
最后，我們檢查“currentSum”是否等于“maxSum”以及當(dāng)前子數(shù)組的大小是否大于前一個(gè)子數(shù)組。如果是，我們將“end”更新為當(dāng)前索引。
第 5 步
該算法的時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)，對(duì)于該問題來說是最優(yōu)的。
示例
下面的 JavaScript 程序旨在解決使用 start 和 end 兩個(gè)指針在整數(shù)數(shù)組中查找總和最大的連續(xù)子數(shù)組的問題。該算法將最大總和初始化為負(fù)無(wú)窮大，將當(dāng)前總和初始化為零，并將起始索引和結(jié)束索引初始化為零。它將每個(gè)元素添加到當(dāng)前總和中，如果當(dāng)前總和大于最大總和，則更新最大總和和結(jié)束索引。它從子數(shù)組的開頭刪除元素，直到當(dāng)前總和不再為負(fù)，然后如果當(dāng)前總和等于最大總和并且子數(shù)組的長(zhǎng)度大于前一個(gè)子數(shù)組的長(zhǎng)度，則更新結(jié)束索引。最后，它通過從結(jié)束索引減去開始索引并加 1 來返回最大子數(shù)組的長(zhǎng)度。
function maxSubarraySize(arr) {
let maxSum = -Infinity;
let currentSum = 0;
let start = 0;
let end = 0;
for (let i = 0; i < arr.length; i++) {
currentSum += arr[i];
if (currentSum > maxSum) {
maxSum = currentSum;
end = i;
}
while (currentSum < 0) {
currentSum -= arr[start];
start++;
}
if (currentSum === maxSum && i - start > end - start) {
end = i;
}
}
return end - start + 1;
}
// Example usage:
const arr = [1, -2, 1, 1, -2, 1];
console.log("Array:", JSON.stringify(arr));
const size = maxSubarraySize(arr);
console.log("Size of the Subarray with Maximum Sum:", size);
登錄后復(fù)制
讓我們通過一些示例查看輸出，以便更好地理解。
示例 1
輸入 – 給定一個(gè)整數(shù)數(shù)組，a[]= {1, -2, 1, 1, -2, 1}
輸出??2
說明 – 具有連續(xù)元素且最大總和為 {1, 1} 的子數(shù)組。因此，長(zhǎng)度為2。
示例 2
輸入 – 給定所有負(fù)整數(shù)的數(shù)組，a[]= {-2, -5, -8, -3, -1, -7}
輸出-1
解釋 – 在這種情況下，最大子數(shù)組將為 [-1]，總和為 -1。因此，子數(shù)組的長(zhǎng)度為-1。
結(jié)論
在編程中使用數(shù)組時(shí)，具有最大和的子數(shù)組的大小是一個(gè)常見問題。解決此問題的算法涉及迭代數(shù)組并跟蹤當(dāng)前總和以及迄今為止看到的最大總和。通過在 JavaScript 中實(shí)現(xiàn)此算法，我們可以編寫一個(gè)程序，該程序可以有效地查找任何給定整數(shù)數(shù)組的最大總和的子數(shù)組的大小。
以上就是JavaScript 程序計(jì)算具有最大和的子數(shù)組的大小的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注www.92cms.cn其它相關(guān)文章！
