JavaScript 程式計算具有最大和的子數組的大小-js教程-PHP中文網

JavaScript 程式計算具有最大和的子數組的大小

王林

發布： 2023-09-15 22:29:04

轉載

1277 人瀏覽過

JavaScript 程序计算具有最大和的子数组的大小

求最大和子陣列大小的 JavaScript 程式是程式設計領域中的常見問題，尤其是在 Web 開發中。問題陳述涉及在給定的一維整數數組中尋找具有最大總和的連續子數組。這也稱為最大子數組問題。解決這個問題在各種應用中都非常有用，例如財務分析、股票市場預測和訊號處理。

在本文中，我們將看到演算法以及使用 JavaScript 實現最大總和的子數組的大小。我們將首先詳細討論該問題，然後繼續使用 JavaScript 程式語言開發逐步解決方案。那麼就讓我們開始吧！

問題陳述

給定一個整數數組，我們必須找到具有最大總和的子數組的長度。

例如，假設我們有一個整數數組：[1, -2, 1, 1, -2, 1]，最大子數組為 [1, 1]，總和為 2。我們可以用結束索引減去起始索引並加 1 來求出該子數組的長度。在本例中，起始索引為 0，結束索引為 1，因此子數組的長度為 2。

另一個例子是所有負整數的陣列：[-2, -5, -8, -3, -1, -7]。在這種情況下，最大子數組將為 [-1]，總和為 -1。由於所有元素均為負數，因此絕對值最小的子數組的總和最大。因此，子數組的長度為-1。

要注意的是，可以有多個最大子數組，每個子數組的總和相同。然而，我們只需要找到其中一個。

演算法

第 1 步

我們先初始化四個變數：“maxSum”為“-Infinity”，“currentSum”為“0”，“start”為“0”，end 為“0”。我們將使用「maxSum」來追蹤到目前為止我們看到的最大總和，「currentSum」來計算我們目前迭代的子數組的總和，「start」來追蹤子數組的起始索引，以及'end' 來追蹤子數組的結束索引。

第 2 步

然後我們使用“for”循環遍歷數組。對於數組中的每個元素，我們將其添加到“currentSum”中。如果 'currentSum' 大於 'maxSum'，我們將 'maxSum' 更新為 'currentSum' 並將 'end' 設定為目前索引。

第 3 步

接下來，我們使用 while 迴圈來檢查「currentSum」是否小於「0」。如果是，我們從「currentSum」中減去「start」處的值，並將「start」加1。這確保了我們始終擁有數組的連續子集。

第 4 步

最後，我們檢查「currentSum」是否等於「maxSum」以及目前子數組的大小是否大於前一個子數組。如果是，我們將「end」更新為目前索引。

第 5 步

此演算法的時間複雜度為 O(n)，空間複雜度為 O(1)，對於此問題來說是最優的。

範例

下面的 JavaScript 程式旨在解決使用 start 和 end 兩個指標在整數陣列中尋找總和最大的連續子陣列的問題。此演算法將最大總和初始化為負無窮大，將目前總和初始化為零，並將起始索引和結束索引初始化為零。它將每個元素添加到當前總和中，如果當前總和大於最大總和，則更新最大總和和結束索引。它從子數組的開頭刪除元素，直到當前總和不再為負，然後如果當前總和等於最大總和並且子數組的長度大於前一個子數組的長度，則更新結束索引。最後，它透過從結束索引減去開始索引並加 1 來傳回最大子數組的長度。

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);

登入後複製

讓我們透過一些範例查看輸出，以便更好地理解。