用於查詢的 JavaScript 程序，用於查找旋轉數組中給定長度的連續子數組的最大總和-js教程-PHP中文網

用於查詢的 JavaScript 程序，用於查找旋轉數組中給定長度的連續子數組的最大總和

WBOY

發布： 2023-09-03 22:41:13

轉載

744 人瀏覽過

用于查询的 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]);
}

登入後複製