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

王林转载: 2023-09-15 22:29:04 834浏览

求最大和子数组大小的 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);

让我们通过一些示例查看输出，以便更好地理解。