Das Maximum-Sub-Array-Problem ist dasselbe wie das Maximum-Slice-Problem. Dieses Tutorial behandelt das Problem mit der Codierung in C++. Die Frage ist: Was ist die maximale Summe einer möglichen Folge aufeinanderfolgender Zahlen innerhalb eines Arrays? Dies kann das gesamte Array bedeuten. Dieses Problem und seine Lösung in jeder Sprache wird als Maximum-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. Ab sofort ist der schnellste Algorithmus für die Lösung in der wissenschaftlichen Gemeinschaft als Kadane-Algorithmus bekannt. Dieser Artikel erklärt Kadanes Algorithmus mit C++.
Datenbeispiele
Betrachten Sie den folgenden Vektor (Array):
Vektor < int > A = { 5 , - 7 , 3 , 5 , - zwei , 4 , - 1 } ;
Das Segment (Sub-Array) mit der maximalen Summe ist die Sequenz {3, 5, -2, 4}, die eine Summe von 10 ergibt. Keine andere mögliche Sequenz, nicht einmal das gesamte Array, ergibt eine Summe von bis zu den Wert 10. Das gesamte Array ergibt eine Summe von 7, was nicht die maximale Summe ist.
Betrachten Sie den folgenden Vektor:
Vektor < int > B = { - zwei , 1 , - 3 , 4 , - 1 , zwei , 1 , - 5 , 4 } ;
Das Segment (Sub-Array) mit der maximalen Summe ist die Sequenz {4, −1, 2, 1}, die eine Summe von 6 ergibt. Beachten Sie, dass es negative Zahlen innerhalb des Sub-Arrays für die maximale Summe geben kann.
Betrachten Sie den folgenden Vektor:
Vektor < int > C = { 3 , zwei , - 6 , 4 , 0 } ;
Der Slice (Sub-Array) mit der maximalen Summe ist die Sequenz {3, 2}, die eine Summe von 5 ergibt.
Betrachten Sie den folgenden Vektor:
Vektor < int > D= { 3 , zwei , 6 , - 1 , 4 , 5 , - 1 , zwei } ;
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 gesamte Array.
Betrachten Sie den folgenden Vektor:
Vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , fünfzehn , 4 , - 8 , - fünfzehn , - 22 } ;
Hier gibt es zwei Teilfelder mit maximalen Summen. Die höhere Summe ist diejenige, die als Lösung (Antwort) für das Maximum-Sub-Array-Problem betrachtet 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 das Slice mit der Summe von 35 die Antwort.
Betrachten Sie den folgenden Vektor:
Vektor < int > F = { - 4 , 10 , fünfzehn , 9 , - 5 , - zwanzig , - 3 , - 12 , - 3 , 4 , 6 , 3 , zwei , 8 , 3 , - 5 , - zwei } ;
Es gibt zwei Teilfelder mit maximalen Summen. Die höhere Summe ist diejenige, die als Lösung für das Maximum-Sub-Array-Problem betrachtet 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 Slice mit der Summe von 34 die Antwort, weil das Problem darin besteht, nach dem Sub-Array mit der höchsten Summe und nicht nach dem Sub-Array mit der höheren Summe zu suchen.
Entwicklung des Kadane-Algorithmus
Die Informationen in diesem Abschnitt des Tutorials sind nicht die Originalarbeit von Kadane. Es ist die eigene Art des Autors, den Algorithmus von Kadane zu lehren. Einer der obigen Vektoren mit seinen laufenden Summen befindet sich in dieser Tabelle:
| Daten | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | fünfzehn | 4 | -8 | -fünfzehn | -22 |
| Laufende Summe | 5 | 12 | 8 | -zwei | -8 | -zwei | 3 | 13 | 8 | 23 | 27 | einundzwanzig | 16 | -6 |
| Index | 0 | 1 | zwei | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf | 12 | 13 |
Die laufende Summe für einen Index ist die Summe aller vorherigen Werte einschließlich der für den Index. Hier gibt es zwei Folgen mit maximalen Summen. Sie sind {5, 7}, was eine Summe von 12 ergibt, und {6, 5, 10, -5, 15, 4}, was eine Summe von 35 ergibt. Die Sequenz, die eine Summe von 35 ergibt, ist das, was gewünscht wird .
Beachten Sie, dass es für die laufenden Summen zwei Spitzen gibt, nämlich die Werte 12 und 27. Diese Spitzen entsprechen den letzten Indizes der beiden Sequenzen.
Die Idee von Kadanes Algorithmus besteht also darin, die laufende Summe zu erstellen und gleichzeitig die maximalen Summen zu vergleichen, wenn sie angetroffen werden, und sich in dem gegebenen Array von links nach rechts zu bewegen.
Ein weiterer Vektor von oben mit seinen laufenden Summen befindet sich in dieser Tabelle:
Es gibt zwei Folgen mit maximalen Summen. Sie sind {10, 15, 9}, was eine Summe von 34 ergibt; und {4, 6, 3, 2, 8, 3}, was eine Summe von 26 ergibt. Die Folge, die die Summe von 34 ergibt, ist das, was gewünscht wird.
Beachten Sie, dass es für die laufenden Summen zwei Spitzen gibt, nämlich die Werte 30 und 13. Diese Spitzen entsprechen den letzten Indizes der beiden Sequenzen.
Auch hier besteht die Idee von Kadanes Algorithmus darin, die laufende Summe zu erstellen und gleichzeitig die maximalen Summen zu vergleichen, wenn sie angetroffen werden, und sich in dem gegebenen Array von links nach rechts zu bewegen.
Code von Kadanes Algorithmus in C++
Der in diesem Abschnitt des Artikels angegebene Code ist nicht unbedingt der, den Kadane verwendet hat. Allerdings ist es durch seinen Algorithmus. Das Programm würde wie viele andere C++-Programme beginnen mit:
#include#include
mit Namensraum std;
Es gibt die Einbindung der iostream-Bibliothek, die für Ein- und Ausgabe zuständig ist. Es wird der Standardnamensraum verwendet.
Die Idee von Kadanes Algorithmus besteht darin, die laufende Summe zu haben, während die maximalen Summen verglichen werden, wenn sie angetroffen werden, und sich in dem gegebenen Array von links nach rechts bewegen. Die Funktion für den Algorithmus lautet:
int maxSunArray ( Vektor < int > & EIN ) {int N = A.Größe ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
zum ( int ich = 1 ; ich < N; i++ ) {
int tempRunTotal = runTotal + A [ ich ] ; // könnte kleiner als A sein [ ich ]
wenn ( EIN [ ich ] > tempRunTotal )
runTotal = A [ ich ] ; // in Fall EIN [ ich ] ist größer als die laufende Summe
anders
runTotal = tempRunTotal;
wenn ( runTotal > maxBetrag ) // Vergleich aller Maximalsummen
maxSum = runTotal;
}
Rückkehr maxAmount;
}
Die Größe N des gegebenen Arrays (Vektors) wird bestimmt. Die Variable maxSum ist eine der möglichen Maximalsummen. Ein Array hat mindestens eine maximale Summe. Die Variable runTotal repräsentiert die laufende Summe an jedem Index. Sie werden beide mit dem ersten Wert des Arrays initialisiert. Wenn in diesem Algorithmus der nächste Wert im Array größer als die laufende Summe ist, wird dieser nächste Wert zur neuen laufenden Summe.
Es gibt eine Haupt-for-Schleife. Das Scannen beginnt bei 1 und nicht bei Null, da die Variablen maxSum und runTotal auf A[0] initialisiert wurden, was das erste Element des angegebenen Arrays ist.
In der for-Schleife ermittelt die erste Anweisung eine temporäre laufende Summe, indem der aktuelle Wert zur kumulierten Summe aller vorherigen Werte addiert wird.
Als nächstes gibt es ein if/else-Konstrukt. Wenn der aktuelle Wert allein größer ist als die bisherige laufende Summe, dann wird dieser Einzelwert zur laufenden Summe. Dies ist besonders praktisch, wenn alle Werte im angegebenen Array negativ sind. In diesem Fall wird allein der höchste negative Wert zum Maximalwert (der Antwort). Wenn der aktuelle Wert allein nicht größer ist als die vorläufige laufende Summe, dann wird die laufende Summe die vorherige laufende Summe plus den aktuellen Wert, – das ist der Else-Teil des if/else-Konstrukts.
Das letzte Codesegment in der for-Schleife wählt zwischen einer beliebigen vorherigen maximalen Summe für eine vorherige Sequenz (Sub-Array) und einer beliebigen aktuellen maximalen Summe für eine aktuelle Sequenz. Daher wird der höhere Wert gewählt. Es kann mehr als eine maximale Sub-Array-Summe geben. Beachten Sie, dass die laufende Summe steigen und fallen würde, wenn das Array von links nach rechts gescannt wird. Er fällt, wenn er auf negative Werte trifft.
Die endgültige gewählte maximale Sub-Array-Summe wird nach der For-Schleife zurückgegeben.
Der Inhalt für eine geeignete C++-Hauptfunktion für die Algorithmusfunktion von Kadane ist:
Vektor < int > A = { 5 , - 7 , 3 , 5 , - zwei , 4 , - 1 } ; // { 3 , 5 , - zwei , 4 } - > 10int ret1 = maxSunArray ( EIN ) ;
cout << ret1 << endl;
Vektor < int > B = { - zwei , 1 , - 3 , 4 , - 1 , zwei , 1 , - 5 , 4 } ; // { 4 , − 1 , zwei , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
Vektor < int > C = { 3 , zwei , - 6 , 4 , 0 } ; // { 3 , zwei } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
Vektor < int > D= { 3 , zwei , 6 , - 1 , 4 , 5 , - 1 , zwei } ; // { 3 , zwei , 6 , - 1 , 4 , 5 , - 1 , zwei } - > 5
int ret4 = maxSunArray ( D ) ;
cout << Netz4 << endl;
Vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , fünfzehn , 4 , - 8 , - fünfzehn , - 22 } ; // { 6 , 5 , 10 , - 5 , fünfzehn , 4 } - > 35
int ret5 = maxSunArray ( UND ) ;
cout << ret5 << endl;
Vektor < int > F = { - 4 , 10 , fünfzehn , 9 , - 5 , - zwanzig , - 3 , - 12 , - 3 , 4 , 6 , 3 , zwei , 8 , 3 , - 5 , - zwei } ; // { 10 , fünfzehn , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << rechts 6 << endl;
Damit wird die Ausgabe sein:
10
6
5
zwanzig
35
3. 4
Jede Zeilenantwort hier entspricht in der Reihenfolge einem bestimmten Array.
Fazit
Die Zeitkomplexität für Kadanes Algorithmus ist O(n), wobei n die Anzahl der Elemente im gegebenen Array ist. Diese Zeitkomplexität ist die schnellste für das Problem der maximalen Teilanordnung. Es gibt andere Algorithmen, die langsamer sind. Die Idee von Kadanes Algorithmus besteht darin, die laufende Summe zu erstellen, während die maximalen Summen verglichen werden, wenn sie angetroffen werden, und sich in dem gegebenen Array von links nach rechts bewegen. Wenn der aktuelle Wert allein größer ist als die bisherige laufende Summe, dann wird dieser Einzelwert zur neuen laufenden Summe. Andernfalls ist die neue laufende Summe wie erwartet die vorherige laufende Summe plus das aktuelle Element, wenn das angegebene Array gescannt wird.
Es kann mehr als eine maximale Summe für unterschiedliche mögliche Unterarrays geben. Die höchste Maximalsumme für alle möglichen Unterarrays wird gewählt.
Was sind die begrenzenden Indizes für den Bereich der gewählten Höchstsumme? – Das ist eine Diskussion für ein andermal!
Chrys