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(QDN)，其中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]);
}