JavaScript-Programm zur Berechnung der Größe eines Subarrays mit maximaler Summe

JavaScript-Programm zum Ermitteln der Maximal- und Subarray-Größe ist ein häufiges Problem im Bereich der Programmierung, insbesondere in der Webentwicklung. Die Problemstellung besteht darin, das zusammenhängende Unterarray mit der maximalen Summe in einem gegebenen eindimensionalen Array von ganzen Zahlen zu finden. Dies wird auch als Maximum-Subarray-Problem bezeichnet. Die Lösung dieses Problems ist in einer Vielzahl von Anwendungen nützlich, beispielsweise bei der Finanzanalyse, Börsenprognosen und der Signalverarbeitung.

In diesem Artikel sehen wir den Algorithmus und die Größe von Subarrays für die maximale Summe mithilfe von JavaScript. Wir besprechen zunächst das Problem im Detail und entwickeln dann Schritt für Schritt eine Lösung mithilfe der Programmiersprache JavaScript. Also fangen wir an!

Problemstellung

Bei einem Array von ganzen Zahlen müssen wir die Länge des Unterarrays mit der maximalen Summe ermitteln.

Angenommen, wir haben ein Array von ganzen Zahlen: [1, -2, 1, 1, -2, 1], das größte Subarray ist [1, 1] und die Summe ist 2. Wir können die Länge dieses Subarrays ermitteln, indem wir den Startindex vom Endindex subtrahieren und 1 addieren. In diesem Beispiel ist der Startindex 0 und der Endindex 1, sodass die Länge des Subarrays 2 beträgt.

Ein weiteres Beispiel ist ein Array aller negativen Ganzzahlen: [-2, -5, -8, -3, -1, -7]. In diesem Fall ist das größte Subarray [-1] und die Summe ist -1. Da alle Elemente negativ sind, hat das Subarray mit dem kleinsten Absolutwert die größte Summe. Daher beträgt die Länge des Subarrays -1.

Es ist zu beachten, dass es mehrere maximale Subarrays mit jeweils derselben Summe geben kann. Wir müssen jedoch nur einen von ihnen finden.

Algorithmus

Schritt 1

Wir initialisieren zunächst vier Variablen: „maxSum“ ist „-Infinity“, „currentSum“ ist „0“, „start“ ist „0“ und end ist „0“. Wir verwenden „maxSum“, um die größte Summe zu verfolgen, die wir bisher gesehen haben, „currentSum“, um die Summe des Subarrays für unsere aktuelle Iteration zu berechnen, „start“, um den Startindex des Subarrays zu verfolgen, und „end“, um den Endindex des Subarrays zu verfolgen.

Schritt 2

Dann verwenden wir eine „for“-Schleife, um das Array zu durchlaufen. Für jedes Element im Array fügen wir es zu „currentSum“ hinzu. Wenn „currentSum“ größer als „maxSum“ ist, aktualisieren wir „maxSum“ auf „currentSum“ und setzen „end“ auf den aktuellen Index.

Schritt 3

Als nächstes verwenden wir eine While-Schleife, um zu prüfen, ob „currentSum“ kleiner als „0“ ist. Wenn ja, subtrahieren wir den Wert bei „start“ von „currentSum“ und addieren 1 zu „start“. Dadurch wird sichergestellt, dass wir immer eine zusammenhängende Teilmenge des Arrays haben.

Schritt 4

Abschließend prüfen wir, ob „currentSum“ gleich „maxSum“ ist und ob die Größe des aktuellen Subarrays größer als die des vorherigen Subarrays ist. Wenn ja, aktualisieren wir „end“ auf den aktuellen Index.

Schritt 5

Die zeitliche Komplexität dieses Algorithmus beträgt O(n) und die räumliche Komplexität beträgt O(1), was für dieses Problem optimal ist.

Beispiel

Das folgende JavaScript-Programm soll das Problem lösen, zwei Zeiger, Start und Ende, zu verwenden, um das zusammenhängende Unterarray mit der größten Summe in einem ganzzahligen Array zu finden. Der Algorithmus initialisiert die maximale Summe auf negative Unendlichkeit, die aktuelle Summe auf Null und die Start- und Endindizes auf Null. Es fügt jedes Element zur aktuellen Summe hinzu und aktualisiert die maximale Summe und den Endindex, wenn die aktuelle Summe größer als die maximale Summe ist. Es entfernt Elemente vom Anfang des Subarrays, bis die aktuelle Summe nicht mehr negativ ist, und aktualisiert dann den Endindex, wenn die aktuelle Summe gleich der Maximalsumme ist und die Länge des Subarrays größer als die Länge des vorherigen Subarrays ist. Schließlich wird die Länge des größten Subarrays zurückgegeben, indem der Startindex vom Endindex subtrahiert und 1 addiert wird.

function maxSubarraySize(arr) {
   let maxSum = -Infinity;
   let currentSum = 0;
   let start = 0;
   let end = 0;
   for (let i = 0; i < arr.length; i++) {
      currentSum += arr[i];
      if (currentSum > maxSum) {
         maxSum = currentSum;
         end = i;
      }
      while (currentSum < 0) {
         currentSum -= arr[start];
         start++;
      }
      if (currentSum === maxSum && i - start > end - start) {
         end = i;
      }
   }
   return end - start + 1;
} 
// Example usage:
const arr = [1, -2, 1, 1, -2, 1];
console.log("Array:", JSON.stringify(arr));
const size = maxSubarraySize(arr);
console.log("Size of the Subarray with Maximum Sum:", size);

Sehen wir uns zum besseren Verständnis die Ausgabe mit einigen Beispielen an.

Beispiel 1

Eingabe – Gegeben ein Array von ganzen Zahlen, a[]= {1, -2, 1, 1, -2, 1}

Ausgabe− 2

Beschreibung – Ein Subarray mit aufeinanderfolgenden Elementen mit einer maximalen Summe von {1, 1}. Daher beträgt die Länge 2.

Beispiel 2

Eingabe – Gegeben ein Array aller negativen Ganzzahlen, a[]= {-2, -5, -8, -3, -1, -7}

Ausgabe-1

Erläuterung – In diesem Fall beträgt das maximale Subarray [-1] und die Summe beträgt -1. Daher beträgt die Länge des Subarrays -1.

Fazit

Die Größe des Subarrays mit der größten Summe ist eine häufige Frage bei der Arbeit mit Arrays in der Programmierung. Der Algorithmus zur Lösung dieses Problems besteht darin, das Array zu durchlaufen und die aktuelle Summe sowie die größte bisher gesehene Summe zu verfolgen. Durch die Implementierung dieses Algorithmus in JavaScript können wir ein Programm schreiben, das effizient die Größe des Subarrays ermittelt, das die größte Summe für ein gegebenes Array von Ganzzahlen aufweist.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zur Berechnung der Größe eines Subarrays mit maximaler Summe. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!