用于查询的 JavaScript 程序，用于查找旋转数组中给定长度的连续子数组的最大总和

旋转数组意味着我们将获得一个数字，并且我们必须以循环顺序向右或向左移动数组的元素。这里我们没有指定，所以我们将以右旋转为标准，在给定的旋转次数后，我们将返回总和最大的子数组。我们将在文章中看到带有正确解释的代码。

问题简介

在这个问题中，我们得到一个包含整数的数组和另一个包含查询对的数组。查询数组的每个索引包含两个整数，第一个整数表示当前数组旋转的次数，第二个整数表示所需子数组的长度。例如 –

如果给定数组是 [ 5, 7, 1, 4, 3, 8, 2] 并且查询如下 –

Queries: 3 rotations and size 3
After the three rotations, the array looks like: 3, 8, 2, 5, 7, 1, 4
From the above array, the result is 15 by subarray: 8, 2, and 5.
Queries: 2 rotations and size 4
After the two rotations, the array looks like: 8, 2, 5, 7, 1, 4, 3
From the above array, the result is 22 by subarrays 8, 2, 5, and 7

登录后复制

让我们转向解决这个问题的方法

天真的方法

最简单的方法是直接使用两个 for 循环来实现给定的问题。首先，我们将在阵列上移动并以顺时针方式旋转它指定的次数。然后我们找到给定大小的子数组以及和最大的子数组。让我们看看它的代码 –

示例

// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
   var n = arr.length 
   var temp = new Array(n)
   var j = 0;
   for(var i = n-rotations; i<n;i++){
      temp[j] = arr[i];
      j++;
   }
   for(var i = 0; i < n-rotations; i++){
      temp[j] = arr[i];
      j++;
   }
   
   // getting the size of the first window of the given size 
   var ans = -1000000000;
   for(var i = 0; i<=n-size; i++) {
      var cur = 0;
      for(var j = i; j < i+size; j++) {
         cur += temp[j];
      }
      if(ans < cur) {
         ans = cur;
      }
   }
   console.log("The maximum sum or given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}

// defining array 
var arr= [5, 7, 1, 4, 3, 8, 2]

// defining quries 
var queries = [[3,3], [2,4]]

// traversing over the array 
for(var i =0; i<queries.length; i++){
   subSum(arr, queries[i][0], queries[i][1]);
}

登录后复制

时间和空间复杂度

上述代码的时间复杂度为O(Q*D*N)，其中Q是查询次数。 D 是每个所需子数组的大小，N 是数组的长度。

上述代码的空间复杂度为 O(N)，因为我们使用额外的数组来存储旋转后的数组。

高效的方法

使用滑动窗口方法可以有效地解决这个问题。让我们直接转向这个问题的代码并通过它获得概述 –

示例

// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
   var n = arr.length 
   var temp = new Array(n)
   var j = 0;
   for(var i = n-rotations; i<n;i++){
      temp[j] = arr[i];
      j++;
   }
   for(var i = 0; i < n-rotations; i++){
      temp[j] = arr[i];
      j++;
   }
   
   // getting the size of the first window of the given size 
   var ans = -1000000000
   var cur = 0;
   for(var i = 0;i<size;i++){
      cur += temp[i];
   }
   ans = cur;
   for(var i = size; i<n;i++){
      cur -= temp[i-size];
      cur += temp[i];
      if(ans < cur) {
         ans = cur;
      }
   }
   console.log("The maximum sum of given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}

// defining array 
var arr= [5, 7, 1, 4, 3, 8, 2]

// defining quries 
var queries = [[3,3], [2,4]]

// traversing over the array 
for(var i =0; i<queries.length; i++){
   subSum(arr, queries[i][0], queries[i][1]);
}

登录后复制

时间和空间复杂度

上述代码的时间复杂度为O(Q*N)，其中Q是查询次数，N是数组长度。

上述代码的空间复杂度为 O(N)，因为我们使用额外的数组来存储旋转后的数组。

结论

在本教程中，我们实现了一个用于查询的 JavaScript 程序，以查找旋转数组中给定长度的连续子数组的最大总和。我们实现了一种时间复杂度为 O(N*Q*D) 的朴素方法，然后通过使用滑动窗口的概念将其改进为 O(N*Q) 时间复杂度，但两个代码的空间复杂度相同 O(N) .

以上就是用于查询的 JavaScript 程序，用于查找旋转数组中给定长度的连续子数组的最大总和的详细内容，更多请关注php中文网其它相关文章！