Program JavaScript untuk pertanyaan mencari jumlah maksimum subarray berturut-turut bagi panjang tertentu dalam tatasusunan diputar

Memutar tatasusunan bermakna kita akan mendapat nombor dan kita perlu menggerakkan elemen tatasusunan ke kanan atau kiri dalam susunan bulat. Di sini kami tidak menyatakan, jadi kami akan menggunakan putaran kanan sebagai kriteria, dan selepas bilangan putaran yang diberikan, kami akan mengembalikan subarray dengan jumlah terbesar. Kami akan melihat kod dengan penjelasan yang betul dalam artikel.

pengenalan masalah

Dalam masalah ini, kita mendapat tatasusunan yang mengandungi integer dan tatasusunan lain yang mengandungi pasangan pertanyaan. Setiap indeks tatasusunan pertanyaan mengandungi dua integer, integer pertama mewakili bilangan putaran tatasusunan semasa, dan integer kedua mewakili panjang subarray yang dikehendaki. Contohnya -

Jika tatasusunan yang diberikan ialah [5, 7, 1, 4, 3, 8, 2] dan pertanyaannya adalah seperti berikut -

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

Mari kita beralih kepada penyelesaian kepada masalah ini

kaedah tidak bersalah

Cara paling mudah ialah dengan terus menggunakan dua gelung untuk melaksanakan masalah yang diberikan. Mula-mula, kita akan bergerak ke atas tatasusunan dan memutarkannya mengikut arah jam beberapa kali tertentu. Kemudian kita dapati subarray dengan saiz tertentu dan subarray dengan jumlah terbesar. Mari lihat kodnya -

Contoh

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

Kerumitan Masa dan Ruang

Kerumitan masa kod di atas ialah O(Q*D*N), dengan Q ialah bilangan pertanyaan. D ialah saiz setiap subarray yang dikehendaki dan N ialah panjang tatasusunan.

Kerumitan ruang kod di atas ialah O(N) kerana kami menggunakan tatasusunan tambahan untuk menyimpan tatasusunan yang diputar.

kaedah yang cekap

Menggunakan kaedah tetingkap gelongsor boleh menyelesaikan masalah ini dengan berkesan. Mari pergi terus ke kod soalan ini dan dapatkan gambaran keseluruhan melaluinya -

Contoh

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

Kerumitan Masa dan Ruang

Kerumitan masa kod di atas ialah O(Q*N), dengan Q ialah bilangan pertanyaan dan N ialah panjang tatasusunan.

Kerumitan ruang kod di atas ialah O(N) kerana kami menggunakan tatasusunan tambahan untuk menyimpan tatasusunan yang diputar.

KESIMPULAN

Dalam tutorial ini, kami melaksanakan program JavaScript untuk membuat pertanyaan untuk mencari jumlah maksimum subarray berturut-turut bagi panjang tertentu dalam tatasusunan diputar. Kami melaksanakan kaedah naif dengan kerumitan masa O(N*Q*D) dan kemudian menambah baiknya kepada kerumitan masa O(N*Q) dengan menggunakan konsep tingkap gelongsor, tetapi kerumitan ruang kedua-dua kod Sama O(N) .

Atas ialah kandungan terperinci Program JavaScript untuk pertanyaan mencari jumlah maksimum subarray berturut-turut bagi panjang tertentu dalam tatasusunan diputar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!