JavaScript program for query to find the maximum sum of consecutive subarrays of given length in a rotated array

Rotating an array means that we will get a number and we have to move the elements of the array to the right or left in a circular order. Here we don't specify, so we will use right rotation as the criterion, and after the given number of rotations, we will return the subarray with the largest sum. We will see the code with correct explanation in the article.

Problem Introduction

In this problem, we get an array containing integers and another array containing query pairs. Each index of the query array contains two integers, the first integer represents the number of rotations of the current array, and the second integer represents the length of the desired subarray. For example -

If the given array is [5, 7, 1, 4, 3, 8, 2] and the query is as follows -

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

Let’s turn to solutions to this problem

Naive method

The simplest way is to directly use two for loops to implement the given problem. First, we will move over the array and rotate it in a clockwise manner a specified number of times. Then we find subarrays of a given size and the subarray with the largest sum. Let's see its code -

Example

// 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]);
}

Time and space complexity

The time complexity of the above code is O(Q*D*N), where Q is the number of queries. D is the size of each desired subarray and N is the length of the array.

The space complexity of the above code is O(N) because we use an extra array to store the rotated array.

Efficient method

Using the sliding window method can effectively solve this problem. Let's go directly to the code of this question and get an overview through it -

Example

// 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]);
}

Time and space complexity

The time complexity of the above code is O(Q*N), where Q is the number of queries and N is the array length.

The space complexity of the above code is O(N) because we use an extra array to store the rotated array.

in conclusion

In this tutorial, we implemented a JavaScript program for querying to find the maximum sum of consecutive subarrays of a given length in a rotated array. We implemented a naive method with time complexity O(N*Q*D) and then improved it to O(N*Q) time complexity by using the concept of sliding windows, but the space complexity of both codes Same O(N) .

The above is the detailed content of JavaScript program for query to find the maximum sum of consecutive subarrays of given length in a rotated array. For more information, please follow other related articles on the PHP Chinese website!