最大和子陣列的大小 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);

讓我們看看一些示例的輸出，以便更好地理解。

示例 1

輸入 - 給定一個整數陣列，a[]= {1, -2, 1, 1, -2, 1}

輸出 − 2

說明 - 具有連續元素且和最大的子陣列是 {1, 1}。因此，長度為 2。

示例 2

輸入 - 給定所有負整數的陣列，a[]= {-2, -5, -8, -3, -1, -7}

輸出-1

說明 - 在這種情況下，最大子陣列將是 [-1]，其和為 -1。因此，子陣列的長度為 -1。

結論

在程式設計中使用陣列時，最大和子陣列的大小是一個常見問題。解決此問題的演算法涉及遍歷陣列並跟蹤當前和以及迄今為止看到的最大和。透過在 JavaScript 中實現此演算法，我們可以編寫一個程式，該程式可以有效地找到任何給定整數陣列的最大和子陣列的大小。