旋轉數組意味著我們將獲得一個數字，並且我們必須以循環順序向右或向左移動數組的元素。這裡我們沒有指定，所以我們將以右旋轉為標準，在給定的旋轉次數後，我們將返回總和最大的子數組。我們將在文章中看到帶有正確解釋的程式碼。
在這個問題中，我們得到一個包含整數的陣列和另一個包含查詢對的陣列。查詢數組的每個索引包含兩個整數，第一個整數表示目前數組旋轉的次數，第二個整數表示所需子數組的長度。例如 -
如果給定數組是 [ 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中文網其他相關文章！
