最大和子数组的大小 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 中实现此算法，我们可以编写一个程序，该程序可以有效地找到任何给定整数数组的最大和子数组的大小。