JavaScript 中数组 n 个连续元素的最大和


在给定的问题陈述中,我们的目标是利用 Javascript 功能找到数组中 n 个连续项的最大和。因此,为了解决这个问题,我们将使用基本的 Javascript 功能并生成最大和。

理解问题

手头的问题是找到数组中 n 个连续项的最大和。此过程将涉及在给定数组中识别长度为 n 的连续子数组,该子数组具有最大可能的和。例如,假设我们有一个数组 [1, 2, 4, 7, 3, 5],因此如果 n 的值为 2,则 2 个连续项为 4、7,最大和为 11。

给定问题的逻辑

为了解决给定的问题,我们将使用一个函数来执行此任务。该函数将在数组的开头初始化两个指针 left 和 right。之后,我们将向右移动 right 指针,并跟踪窗口内项的当前和。现在,我们将检查条件,如果窗口的大小大于 n,我们将从当前和中减去 left 指针处项的值。然后,我们将向右移动 left 指针。因此,我们将始终保持大小为 n 的窗口,并根据条件更新最大和。

算法

步骤 1:由于我们必须找到数组中 n 个连续项的最大和,因此为了执行此任务,我们将创建一个函数并将其命名为 maxSumOfNElements。此函数接受两个参数:第一个是数组 arr,第二个是数字 n。

步骤 2:因此,在上述函数中,我们将首先检查 n 的值是否大于数组的长度。如果条件为真,则返回 null 值,因为它不是有效的输入。

步骤 3:验证上述条件后,我们将初始化两个变量 maxSum 和 currentSum 为零。maxSum 将存储连续元素的最大和,currentSum 将存储 n 个连续项的运行和。

步骤 4:由于我们已声明将在这些步骤中使用的变量。现在,我们将计算数组中前 n 个项的初始和,并将其保存在 maxSum 和 currentSum 变量中。

步骤 5:此步骤将使用 for 循环遍历数组,并从索引 n 开始。

步骤 6:在循环中,我们将添加当前项并从 currentSum 中减去位于 n 个位置之后的项。

步骤 7:现在,我们将使用 maxSum 和 currentSum 之间的最大值更新 maxSum。

步骤 8:完成循环后,我们将返回数组中 n 个连续项的最大和。

示例

//Function to find the maximum sum
function maxSumOfNElements(arr, n) {
   if (n > arr.length) {
      return null; // Invalid input, as n is larger than array size
   }

   let maxSum = 0;
   let currentSum = 0;

   for (let i = 0; i < n; i++) {
      maxSum += arr[i];
   }
   currentSum = maxSum;

   for (let i = n; i < arr.length; i++) {
      currentSum += arr[i] - arr[i - n];
      maxSum = Math.max(maxSum, currentSum);
   }

   return maxSum;
}

const arr = [1, 3, 5, 2, 4, 6, 8];
const n = 3;
const result = maxSumOfNElements(arr, n);
console.log("Maximum sum of", n, "consecutive items:", result);

输出

Maximum sum of 3 consecutive items: 18

复杂度

计算数组中存在的 n 个连续项的最大和的时间复杂度为 O(n),其中 n 是数组的长度。因为我们只遍历了数组一次。上述代码的空间复杂度为 O(1),因为我们只使用了恒定数量的空间来存储变量。

结论

我们已有效地找到了数组中 n 个连续项的最大和。这种方法用于以线性时间复杂度解决问题,对于大型数组来说是一种有效的解决方案。

更新于: 2023-08-16

784 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始
广告