Maximales Sub-Array-Problem in C ++

Das maximale Problem des Sub-Array-Problems ist das gleiche wie ein maximales Slice-Problem. In diesem Tutorial wird das Problem bei der Codierung in C erörtert++. Die Frage ist: Was ist die maximale Summe einer möglichen Abfolge von aufeinanderfolgenden Zahlen innerhalb eines Arrays? Dies kann das gesamte Array bedeuten. Dieses Problem und seine Lösung in jeder Sprache werden als maximales Sub-Array-Problem bezeichnet. Das Array kann mögliche negative Zahlen haben.

Die Lösung muss effizient sein. Es muss die schnellste Zeitkomplexität haben. Der schnellste Algorithmus für die Lösung ist in der wissenschaftlichen Gemeinschaft als Kadanes Algorithmus bekannt. Dieser Artikel erklärt Kadanes Algorithmus mit C++.

Datenbeispiele

Betrachten Sie den folgenden Vektor (Array):

Vektor A = 5, -7, 3, 5, -2, 4, -1;

Die Scheibe (Sub -Array) mit der maximalen Summe ist die Sequenz, 3, 5, -2, 4, die eine Summe von 10 ergibt. Keine andere mögliche Sequenz, auch das gesamte Array, gibt eine Summe von bis zum Wert von 10. Das gesamte Array ergibt eine Summe von 7, was nicht die maximale Summe ist.

Betrachten Sie den folgenden Vektor:

Vektor B = -2, 1, -3, 4, -1, 2, 1, -5, 4;

Die Scheibe (Sub-Array) mit der maximalen Summe ist die Sequenz 4, –1, 2, 1, die eine Summe von 6 ergibt. Beachten Sie, dass es im Sub-Array negative Zahlen für maximale Summe geben kann.

Betrachten Sie den folgenden Vektor:

Vektor C = 3, 2, -6, 4, 0;

Die Scheibe (Sub-Array) mit der maximalen Summe ist die Sequenz 3, 2, die eine Summe von 5 ergibt.

Betrachten Sie den folgenden Vektor:

Vektor D = 3, 2, 6, -1, 4, 5, -1, 2;

Das Sub -Array mit der maximalen Summe ist die Sequenz, 3, 2, 6, -1, 4, 5, -1, 2, die eine Summe von 20 ergibt. Es ist das ganze Array.

Betrachten Sie den folgenden Vektor:

Vektor E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22;

Hier gibt es zwei Unterarrays mit maximalen Summen. Die höhere Summe ist diejenige, die als Lösung (Antwort) für das maximale Sub-Array-Problem angesehen wird. Die Sub -Arrays sind: 5, 7 mit einer Summe von 12 und 6, 5, 10, -5, 15, 4 mit einer Summe von 35. Natürlich ist die Scheibe mit der Summe von 35 die Antwort.

Betrachten Sie den folgenden Vektor:

Vektor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2;

Es gibt zwei Unterarrays mit maximalen Summen. Die höhere Summe ist diejenige, die als Lösung für das maximale Sub-Array-Problem angesehen wird. Die Sub-Arrays sind: 10, 15, 9 mit einer Summe von 34 und 4, 6, 3, 2, 8, 3 mit einer Summe von 26. Natürlich ist das Schicht mit der Summe von 34 die Antwort, da das Problem darin besteht.

Entwicklung von Kadanes Algorithmus

Die Informationen in diesem Abschnitt des Tutorials sind nicht die ursprüngliche Arbeit von Kadane. Es ist die eigene Art des Autors, Kadanes Algorithmus zu unterrichten. Einer der oben genannten Vektoren mit seinen laufenden Gesamtsummen befindet sich in dieser Tabelle:

Das Ausführen der Gesamtsumme für einen Index ist die Summe aller früheren Werte, einschließlich der für den Index. Hier gibt es zwei Sequenzen mit maximalen Summen. Sie sind 5, 7, die eine Summe von 12 und 6, 5, 10, -5, 15, 4 angeben, was eine Summe von 35 ergibt. Die Sequenz, die eine Summe von 35 ergibt, ist das, was gewünscht wird.

Beachten Sie, dass für die Laufsummen zwei Peaks die Werte sind, 12 und 27, sind. Diese Peaks entsprechen den letzten Indizes der beiden Sequenzen.

Die Idee von Kadanes Algorithmus besteht also darin, die Gesamtsumme durchzuführen, während sie die maximalen Summen vergleicht.

Ein weiterer Vektor von oben mit seinen laufenden Gesamtsummen befindet sich in dieser Tabelle:

Es gibt zwei Sequenzen mit maximalen Summen. Sie sind 10, 15, 9, was eine Summe von 34 ergibt; und 4, 6, 3, 2, 8, 3, die eine Summe von 26 ergibt. Die Sequenz, die die Summe von 34 ergibt, ist das, was gewünscht wird.

Beachten Sie, dass es für die Laufsummen zwei Peaks gibt, die die Werte 30 und 13 sind. Diese Peaks entsprechen den letzten Indizes der beiden Sequenzen.

Auch hier besteht die Idee von Kadanes Algorithmus darin, die Gesamtsumme durchzuführen und die maximalen Summen zu vergleichen, sobald sie auftreten, und bewegen.

Code von Kadanes Algorithmus in C++

Der in diesem Abschnitt des Artikels angegebene Code ist nicht unbedingt das, was Kadane verwendet hat. Es ist jedoch durch seinen Algorithmus. Das Programm würde wie viele andere C ++ - Programme beginnen mit:

#enthalten
#enthalten

Verwenden von Namespace STD;

Es gibt die Einbeziehung der iOstream -Bibliothek, die für Eingabe und Ausgabe verantwortlich ist. Der Standard -Namespace wird verwendet.

Die Idee von Kadanes Algorithmus besteht darin, die Gesamtsumme zu haben, während sie die maximalen Summen vergleicht. Die Funktion für den Algorithmus lautet:

int maxsunarray (Vektor &A)
int n = a.Größe();
int maxsum = a [0];
int runtotal = a [0];
für (int i = 1; i < N; i++)
int tempruntotal = runtotal + a [i]; // könnte kleiner sein als a [i]
if (a [i]> tempruntotal)
Runtotal = a [i]; // falls a [i] größer ist als die totale Läufe
anders
Runtotal = Tempruntotal;
if (runtotal> maxsum) // Vergleiche alle maximalen Summen
maxsum = runtotal;

MAXSUM zurückgeben;

Die Größe n des angegebenen Arrays (Vektor) wird bestimmt. Die Variable, Maxsum ist einer der möglichen maximalen Summen. Ein Array hat mindestens eine maximale Summe. Die Variable, Runtotal repräsentiert die laufende Gesamtsumme bei jedem Index. Sie werden beide mit dem ersten Wert des Arrays initialisiert. In diesem Algorithmus wird der nächste Wert der nächste Wert zur neuen laufenden Gesamtsumme, wenn der nächste Wert im Array größer ist als der laufende Gesamtwert.

Es gibt einen Hauptverschluss. Das Scannen beginnt von 1 und nicht Null aufgrund der Initialisierung der Variablen, Maxsum und Runtotal zu einem [0], das das erste Element des angegebenen Arrays.

In der FOR-Schleife bestimmt die erste Anweisung eine vorübergehende Gesamtsumme, indem der aktuelle Wert zur akkumulierten Summe aller früheren Werte hinzugefügt wird.

Als nächstes gibt es ein If/sonst -Konstrukt. Wenn der aktuelle Wert allein größer ist als die bisher laufende Gesamtsumme, wird dieser Einzelwert zum laufenden Gesamtwert. Dies ist praktisch, besonders wenn alle Werte im angegebenen Array negativ sind. In diesem Fall wird der höchste negative Wert allein zum Maximalwert (die Antwort). Wenn der aktuelle Wert allein nicht größer ist als die bisherige vorübergehende Gesamtsumme, wird die laufende Gesamtsumme zum vorherigen laufenden Gesamtwert des aktuellen Wert.

Das letzte Code-Segment in der FOR-Loop wählt zwischen einer vorherigen maximalen Summe für eine vorherige Sequenz (Sub-Array) und einer maximalen Stromsumme für eine Stromsequenz aus. Der höhere Wert wird daher gewählt. Es kann mehr als eine maximale Sub-Array-Summe geben. Beachten Sie, dass die laufende Gesamtzahl steigen und fallen würde, wenn das Array von links nach rechts gescannt wird. Es fällt, da es negative Werte erfüllt.

Die endgültige gewählte maximale Sub-Array-Summe wird nach dem For-Loop zurückgegeben.

Der Inhalt für eine geeignete C ++ -Kennfunktion für die Funktion des Kadane -Algorithmus ist:

Vektor A = 5, -7, 3, 5, -2, 4, -1; // 3, 5, -2, 4 -> 10
int ret1 = maxsunarray (a);
Cout << ret1 << endl;
Vektor B = -2, 1, -3, 4, -1, 2, 1, -5, 4; // 4, –1, 2, 1 -> 6
int ret2 = maxsunarray (b);
Cout << ret2 << endl;
Vektor C = 3, 2, -6, 4, 0; // 3, 2 -> 5
int ret3 = maxsunarray (c);
Cout << ret3 << endl;
Vektor D = 3, 2, 6, -1, 4, 5, -1, 2; // 3, 2, 6, -1, 4, 5, -1, 2 -> 5
int ret4 = maxsunarray (d);
Cout << ret4 << endl;
Vektor E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22; // 6, 5, 10, -5, 15, 4 -> 35
int ret5 = maxsunarray (e);
Cout << ret5 << endl;
Vektor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2; // 10, 15, 9-> 34
int ret6 = maxsunarray (f);
Cout << ret6 << endl;

Damit wird die Ausgabe sein:

10

6

5

20

35

34

Jede Zeilenantwort hier entspricht einem bestimmten Array, damit in der Reihenfolge.

Abschluss

Die zeitliche Komplexität für Kadanes Algorithmus ist O (n), wobei n die Anzahl der Elemente im angegebenen Array ist. Diese Zeit ist die Komplexität für das maximale Sub-Array-Problem am schnellsten. Es gibt andere Algorithmen, die langsamer sind. Die Idee von Kadanes Algorithmus besteht darin, die laufende Gesamtsumme zu erledigen. Wenn der aktuelle Wert allein größer ist als die bisher laufende Gesamtsumme, wird dieser einzelne Wert zur neuen laufenden Gesamt. Andernfalls ist die neue laufende Gesamtsumme die vorherige laufende Gesamtsumme plus das aktuelle Element wie erwartet, da das angegebene Array gescannt wird.

Es kann mehr als eine maximale Summe für verschiedene mögliche Sub-Arrays geben. Die höchste maximale Summe für alle möglichen Unterarrays wird ausgewählt.

Was sind die begrenzenden Indizes für den Bereich der gewählten maximalen Summe? - Das ist eine Diskussion für einige andere Zeit!

Chrys