JavaScript-Programm zur Abfrage, um die maximale Summe aufeinanderfolgender Subarrays einer bestimmten Länge in einem gedrehten Array zu ermitteln

Wenn wir ein Array drehen, erhalten wir eine Zahl und müssen die Elemente des Arrays kreisförmig nach rechts oder links verschieben. Hier geben wir nichts an, daher verwenden wir die Rechtsdrehung als Kriterium und geben nach der angegebenen Anzahl von Drehungen das Subarray mit der größten Summe zurück. Wir werden den Code mit korrekter Erklärung im Artikel sehen.

Einführung in das Problem

In diesem Problem erhalten wir ein Array mit Ganzzahlen und ein weiteres Array mit Abfragepaaren. Jeder Index des Abfragearrays enthält zwei Ganzzahlen. Die erste Ganzzahl repräsentiert die Anzahl der Umdrehungen des aktuellen Arrays und die zweite Ganzzahl repräsentiert die Länge des gewünschten Unterarrays. Zum Beispiel -

Wenn das angegebene Array [5, 7, 1, 4, 3, 8, 2] ist und die Abfrage wie folgt lautet -

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

Lassen Sie uns Lösungen für dieses Problem finden

Naive Methode

Der einfachste Weg besteht darin, zwei for-Schleifen direkt zu verwenden, um das gegebene Problem zu implementieren. Zuerst bewegen wir uns über das Array und drehen es eine bestimmte Anzahl von Malen im Uhrzeigersinn. Dann finden wir Subarrays einer bestimmten Größe und das Subarray mit der größten Summe. Sehen wir uns den Code an -

Beispiel

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(Q*D*N), wobei Q die Anzahl der Abfragen ist. D ist die Größe jedes gewünschten Unterarrays und N ist die Länge des Arrays.

Die räumliche Komplexität des obigen Codes beträgt O(N), da wir ein zusätzliches Array zum Speichern des gedrehten Arrays verwenden.

Effiziente Methode

Die Verwendung der Schiebefenstermethode kann dieses Problem effektiv lösen. Gehen wir direkt zum Code dieser Frage und verschaffen uns einen Überblick darüber -

Beispiel

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(Q*N), wobei Q die Anzahl der Abfragen und N die Array-Länge ist.

Die räumliche Komplexität des obigen Codes beträgt O(N), da wir ein zusätzliches Array zum Speichern des gedrehten Arrays verwenden.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm zur Abfrage implementiert, um die maximale Summe aufeinanderfolgender Subarrays einer bestimmten Länge in einem gedrehten Array zu ermitteln. Wir haben eine naive Methode mit der Zeitkomplexität O(N*Q*D) implementiert und sie dann mithilfe des Konzepts von Schiebefenstern auf die Zeitkomplexität O(N*Q) verbessert, wobei die räumliche Komplexität beider Codes jedoch mit O(N) identisch ist ) .

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zur Abfrage, um die maximale Summe aufeinanderfolgender Subarrays einer bestimmten Länge in einem gedrehten Array zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!