JavaScript-Programm zum Ermitteln der maximalen Summe von i*arr unter allen Rotationen eines bestimmten Arrays

In diesem Artikel implementieren wir ein JavaScript-Programm, um die maximale Summe von i*arr[i] unter allen Rotationen eines bestimmten Arrays zu ermitteln. Hier bedeutet i*arr[i], dass wir die Summe aller Elemente des Arrays maximieren wollen, indem wir sie mit dem Element an der aktuellen Position multiplizieren. Wir können die angegebenen Array-Elemente nach links oder rechts drehen, um die maximale Antwort zu erhalten. Für diese Frage stellen wir einen vollständigen Code und eine detaillierte Erklärung bereit.

Einführung in das Problem

In dieser Frage erhalten wir ein Array. Wenn wir alle Elemente mit ihren entsprechenden Indexnummern multiplizieren und dann die Summe aller Elemente addieren, erhalten wir eine Zahl. Mit einer Drehung können wir das Element ganz links oder ganz rechts auf die gegenüberliegende Seite des Arrays verschieben, wodurch sich der Index jedes Elements ändert, und wir können das Array beliebig oft drehen (aber nachdem die Anzahl der Drehungen gleich ist). Durch Drehen des Arrays können wir den Index der Elemente und damit die Summe von i*arr[i] ändern.

Wir werden versuchen, die Summe mit zwei Ansätzen zu maximieren. Schauen wir uns zunächst das Beispiel an −

Given array: 1 3 2 4 2
0th rotation sum: 1*0 + 3*1 + 2*2 + 4*3 + 2*4 = 27
1st rotation sum:  2*0 + 1*1 + 3*2 + 2*3 + 4*4  = 29
2nd rotation sum: 4*0 + 2*1 + 1*2 + 3*3 + 2*4 = 21
3rd rotation sum: 2*0 + 4*1 + 2*2 + 1*3 + 3*4 = 23 
4th rotation sum: 3*0 + 2*1 + 4*2 + 2*3 + 1*4 = 20

Wir können sehen, dass wir bei der ersten Rotation die höchste Summe erhalten, nämlich den 29.

Methode

Es gibt zwei Möglichkeiten, die erforderliche Summe zu finden. Schauen wir uns beide an -

Methode 1 ist der naive Ansatz. Wir finden alle Rotationen des Arrays in O(N)-Zeit und für jede Rotation ermitteln wir die Summe aller Elemente in O(N)-Zeit, indem wir das Array durchlaufen, während dies nicht der Fall ist Nutzen Sie den zusätzlichen Platz.

Beispiel

// function to find the maximum rotation sum
function maxSum(arr){
   var len = arr.length
   var ans = -10000000000 // variable to store the answer

   // for loop to find all the rotations of the array
   for(var i = 0; i < len; i++) {
      var cur_sum = 0;
      for(var j = 0; j <len ;j++) {
         cur_sum += j*arr[j];
      }
      if(ans < cur_sum){
         ans = cur_sum;
      }
      var temp = arr[len-1];
      var temp2
      for(var j=0; j<len; j++){
         temp2 = arr[j];
         arr[j] = temp;
         temp = temp2
      }
   }
   console.log("The required maximum sum is: " + ans)
}

// defining the array
arr = [1, 3, 2, 4, 2]
maxSum(arr)

Zeitkomplexität und Raumkomplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N*N), wobei N die Größe des Arrays ist und die räumliche Komplexität des obigen Codes O(1) ist.

Bei jeder Iteration gibt es nur einen Unterschied von einem einzelnen Faktor für das letzte Element, nur weil sein Faktor von der Array-Länge aktualisiert wird – 1 auf 0 für die anderen Elemente wird ein weiterer Faktor hinzugefügt, sodass wir Code schreiben können −

Beispiel

// function to find the maximum rotation sum
function maxSum(arr){
   var len = arr.length
   var ans = -10000000000 // variable to store the answer
   
   // for loop to find all the rotations of the array
   var total_sum = 0;
   for (var i=0; i<len; i++){
      total_sum += arr[i];
   }
   var cur_val = 0;
   for (var i=0; i<len; i++){
      cur_val += i*arr[i];
   }
   
   // Initialize result
   var ans = cur_val;
   
   // Compute values for other iterations
   for (var i=1; i<len; i++) {
      var val = cur_val - (total_sum - arr[i-1]) + arr[i-1] * (len-1);
      cur_val = val;
      if(ans < val) {
         ans = val
      }
   }
   console.log("The required maximum sum is: " + ans)
}

// defining the array
arr = [1, 3, 2, 4, 2]
maxSum(arr)

Zeitkomplexität und Raumkomplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Größe des Arrays ist und die räumliche Komplexität des obigen Codes O(1) ist. Dieser Ansatz ist im Vergleich zum vorherigen sehr besser.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um die maximale Summe von i*arr[i] unter allen Rotationen eines bestimmten Arrays zu ermitteln. Wir haben zwei Methoden gesehen: Die eine besteht darin, alle Rotationen eines bestimmten Arrays zu finden und dann die Ergebnisse ihrer i*arr[i]-Ausdrücke zu vergleichen. Bei der zweiten Methode reduzieren wir die Zeitkomplexität mithilfe mathematischer Methoden von O(N*N) auf O(N).

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Ermitteln der maximalen Summe von i*arr unter allen Rotationen eines bestimmten Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!