旋转数组意味着我们将获得一个数字，并且我们必须以循环顺序向右或向左移动数组的元素。这里我们没有指定，所以我们将以右旋转为标准，在给定的旋转次数后，我们将返回总和最大的子数组。我们将在文章中看到带有正确解释的代码。
在这个问题中，我们得到一个包含整数的数组和另一个包含查询对的数组。查询数组的每个索引包含两个整数，第一个整数表示当前数组旋转的次数，第二个整数表示所需子数组的长度。例如 -
如果给定数组是 [ 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中文网其他相关文章！
