© Jirsak/Shutterstock.com
Wenn Sie mit Datensätzen arbeiten, liegen diese wahrscheinlich in Form eines Arrays vor. Und diese Arrays sind oft zusammenhängend. Das bedeutet, dass es keine „Unterbrechungen“ zwischen den Datenwerten gibt – sie werden in einem einzigen Speicherblock gespeichert. Diese Art von Array steht im Mittelpunkt, wenn es um das klassische Maximum-Subarray-Problem geht. Es gibt zwar einige Möglichkeiten, dieses Problem anzugehen, aber eine der besten Möglichkeiten, damit umzugehen, ist die Verwendung des Kadane-Algorithmus. Wenn Sie sich fragen, wie Sie diesen Algorithmus verwenden und wie er in den Bereich der dynamischen Programmierung passt, sind Sie hier richtig. Kommen Sie mit uns, wenn wir Kadanes Algorithmus untersuchen und wie er verwendet wird, um das Maximum-Subarray-Problem zu lösen.
Was ist das Maximum-Subarray-Problem?
Das Maximum-Subarray-Problem ist auch als Maximum bekannt Kontinuierliches Subarray-Problem. Einfach ausgedrückt besteht die Aufgabe dieses Problems darin, das maximal zusammenhängende Subarray innerhalb eines Arrays, arr[], der Größe N zu finden. Das heißt, die maximal mögliche Summe aus dem Hinzufügen von ganzen Zahlen im Array ohne Unterbrechungen zwischen ihnen zu finden. Wenn wir zum Beispiel ein Array [4,-1, 2, 1] nehmen, wäre die maximale Summe einfach die Summe aller ganzen Zahlen oder 6.
Bei kleinen Datensätzen kann dies eine relativ einfache Aufgabe sein, und lässt sich relativ einfach mit dem sogenannten „Brute-Force-Ansatz“ lösen. Dies bedeutet im Grunde, einfachste Berechnungen auf Kosten der Gesamteffizienz zu verwenden. Auf diese Weise können wir beim 0-ten Index beginnen und die Summe aller möglichen Subarrays berechnen, beginnend mit Element A[0]. Wir können diese Subarray-Summen beginnend mit A[1] bis A[n-1] berechnen, wobei n die Array-Größe ist. Wenn wir die maximale Summe eines Subarrays local_maximum bei Index i nennen, können wir all diese berechnen und dann zum Schluss das Maximum der local_maximums finden. Dadurch erhalten wir die größtmögliche Summe, die als global_maximum beschrieben werden kann.
Wie Sie erwarten können, funktioniert dies für sehr kleine Arrays ziemlich gut, ist aber für größere Datensätze ziemlich ineffizient. Die Zeitkomplexität ist quadratisch, oder O(n2), was bedeutet, dass die Komplexität ziemlich schnell mit zunehmender Eingabegröße zunimmt. Daher brauchen wir einen effizienteren und eleganteren Prozess. Hier kommt die dynamische Programmierung ins Spiel.
Wie kann die dynamische Programmierung helfen?
Die dynamische Programmierung ist ein Ansatz zur Lösung komplizierter Probleme, indem sie auf eine Sammlung einfacherer Probleme reduziert werden. Diese einfacheren Probleme werden gelöst, und ihre Lösungen werden in einer Datenstruktur wie einem Array gespeichert. Auf diese Lösungen kann dann zugegriffen werden, wenn wir die gleiche Art von Problem lösen, wodurch vermieden wird, dass sie erneut gelöst werden müssen, und die gesamten Berechnungen beschleunigt werden.
Es wäre wirklich vorteilhaft, wenn wir die Prinzipien anwenden könnten der dynamischen Programmierung zu unserem Maximum-Subarray-Problem. Glücklicherweise können wir das, und genau das ist es, was der Algorithmus von Kadane vorhat. Fangen wir also an.
Dynamische Programmierung ist ein Ansatz zur Lösung komplizierter Probleme, indem sie auf eine Sammlung einfacherer Probleme reduziert werden.
©hafakot/Shutterstock.com
Kadanes Algorithmus
Wie kurz erwähnt, verwendet der Kadane-Algorithmus dynamische Programmierung, um eine effiziente Lösung für das Maximum-Subarray-Problem zu berechnen. Der Algorithmus funktioniert, indem er das zusammenhängende Subarray mit der maximalen Summe am aktuellen Index speichert. Diese wird dann mit der bisher gefundenen Maximalsumme verglichen. Wenn es größer als die bisher gefundene maximale Summe ist, wird es mit dem neuen Wert aktualisiert.
Ein großer Vorteil des Kadane-Algorithmus ist seine Geschwindigkeit, die sich in seiner Zeitkomplexität von O(n) zeigt. Das bedeutet, dass die Zeitkomplexität mit zunehmender Eingabegröße linear zunimmt, was viel besser ist als die quadratische Zeitkomplexität des Brute-Force-Ansatzes. Die Raumkomplexität ist auch gut, da der Algorithmus stabil ist – das bedeutet, dass während des Prozesses eine konstante Menge an Speicher benötigt wird, da nur zwei Variablen gespeichert werden müssen (das sind global_maximum und local_maximum).
Kadanes Algorithmus in Aktion
Nehmen wir wieder das Array [4,-1, 2, 1]. Wenn wir den Brute-Force-Ansatz umkehren und mit dem Element A[n] (in diesem Fall 1) beginnen, können wir die Summe aller möglichen Subarrays berechnen und dann mit A[n-1], A[n-2] fortfahren. bis wir sie alle abgeschlossen haben.
Wenn wir uns die letzten beiden Elemente A[3] und A[4] ansehen, können wir sehen, dass local_maximum 5 bzw. 6 ist. Aber wenn wir local_maximum[3] kennen, müssen wir nicht alle Subarray-Summen für A[4] berechnen. Das liegt daran, dass wir bereits die Ergebnisse von A[3] und dem local_maximum[3] kennen. Wir müssen nur zwei Subarrays überprüfen, dasjenige, das A[4] allein und die Summe von A[4] und local_maximum[3] enthält. In diesem Fall wäre dies A[4} + local_maximum[3], also 6. Dies ist die gleiche Antwort, die wir erhalten, wenn wir alle Subarray-Summen für A[4] berechnen.
Dieses Prinzip ist die Grundlage von Kadanes Algorithmus und kann wie folgt beschrieben werden:
local_maximum[i]=max(A[i], A[i] + local_maximum[i-1])
Oder mit anderen Worten: das local_maximum bei Index i ist das Maximum von A[i] und die Summe von A[i] und local_maximum bei Index i-1.
Also müssen wir nur das Maximum von A[i] finden und A[i] + local_maximum[i-1], um das Maximum bei jedem Index i zu finden. Daher müssen wir nur jedes local_maximum finden, um das maximale Subarray zu finden. Dies ist ein viel effizienterer Weg, um das Maximum-Subarray-Problem anzugehen.
Die Funktionsweise des Kadane-Algorithmus
Lassen Sie uns die Schritte durchgehen, die der Kadane-Algorithmus verwendet, um das maximale Subarray zu berechnen.
p> Der Algorithmus benötigt nur eine Schleife, die von i[0[ bis i[n-1] iteriert. Das local_maximum[i] wird für jedes Element berechnet, das von local_maximum[i-1] abhängt. Das local_maxium wird verglichen bis zum globalen_maximum. Wenn es größer ist, wird global_maximum aktualisiert. Dies wird für jeden Index wiederholt, bis die größte Summe eines zusammenhängenden Subarrays gefunden ist.
Implementierung des Kadane-Algorithmus
Um zu zeigen, wie der Kadane-Algorithmus implementiert werden kann, verwenden wir Python in der Spyder-Umgebung. Schauen wir uns an, wie der Code in der Praxis funktioniert.
from sys import maxsize def solveMaxSubArrayProblem(input): n=len(input) globalMaxSum=-maxsize-1 localMaxSum=0 for i in range(0, n): localMaxSum=max(input[i], input[i] + localMaxSum) if(localMaxSum>globalMaxSum): globalMaxSum=localMaxSum return globalMaxSum if_name_==”_main_”input=[1,-2, 5,-3, 4,-1, 6] result=solveMaxSubArrayProblem(input) print(result) 11
Erstens ist die richtige Einrückung in Python der Schlüssel zur korrekten Ausführung des Codes. Zunächst importieren wir die „maxsize“-Funktion, die verwendet wird, um den Maximalwert zu ermitteln.
Als Nächstes definieren wir „solveMaxSubArrayProblem“ als Funktion des „input“-Arrays der Länge n , wobei globalMaxSum als minimaler ganzzahliger Wert initialisiert wird. Dies geschieht, um sicherzustellen, dass jede berechnete Subarray-Summe größer als dieser Wert ist.
Das local_maximum variiert und wird anfänglich auf 0 gesetzt.
„for“ bezieht sich auf eine Schleife, die verwendet wird, um jedes Array-Element zu durchlaufen.
Für jede Iteration wird „localMaxSum“ entweder auf die localMaxSum des aktuellen Elements oder das Element plus die vorherige localMaxSum aktualisiert.
If localMaxSum größer als die aktuelle globalMaxSum ist, wird letztere aktualisiert, um diese Änderung widerzuspiegeln.
Sobald der iterative Prozess abgeschlossen ist, ist globalMaxSum gleich dem maximalen zusammenhängenden Subarray, und dieses Ergebnis wird zurückgegeben.
Letztlich testet „if __name__==„“__main__““ die Funktion, indem das folgende Array erstellt und die definierte Funktion darauf angewendet wird, und dann das Ergebnis ausgibt.
Für das Array [1 ,-2, 5,-3, 4,-1, 6] hat das maximal zusammenhängende Subarray eine Summe von 11.
©”TNGD”.com
Zusammenfassung
Wir haben das Prinzip der dynamischen Programmierung behandelt. Wir haben auch gezeigt, wie der Algorithmus von Kadane dies verwendet, um das Maximum-Subarray-Problem zu lösen. Die Vorteile davon wurden beschrieben. Der Algorithmus von Kadane ist relativ einfach zu verstehen und zu verwenden, mit effizienter Zeit-und Raumkomplexität. Wenn es darum geht, das Maximum-Subarray-Problem zu lösen, ist Kadanes Algorithmus einer der schnellsten Wege, dies zu tun.
Als Nächstes …
Kadanes Algorithmus: Ein effizienter Ansatz für das Maximum-Subarray-Problem , erklärt mit Fotos FAQs (häufig gestellte Fragen)
Was ist ein Subarray?
Ein Subarray ist Teil eines Arrays, das ununterbrochen ist, d. h. ohne Unterbrechungen zwischen ganzen Zahlen. Dies wird als zusammenhängend beschrieben. Ein Subarray kann aus einem Element bestehen. Sie werden hauptsächlich bei der Arbeit mit Datensätzen verwendet, um beispielsweise das maximal zusammenhängende Subarray zu finden.
Was ist dynamische Programmierung?
Dynamische Programmierung bezieht sich darauf zu einer Technik zur Lösung komplexer Probleme, indem sie in einfachere zerlegt werden. Jede Teillösung muss nur einmal berechnet werden und wird in einem temporären Cache gespeichert. Somit werden redundante Berechnungen vermieden, wodurch Prozesse deutlich beschleunigt werden. Dynamische Programmierung wird häufig verwendet, um Lösungen zu optimieren und Algorithmen zu entwerfen, wie z. B. den Bellman-Ford-Algorithmus zum Finden des kürzesten Pfads in einem Diagramm. Normalerweise werden Teilprobleme von unten nach oben gelöst, was bedeutet, dass die einfachsten Probleme zuerst gelöst werden. Diese Lösungen werden dann kombiniert, um das anfängliche Problem zu lösen.
Was ist das Maximum-Subarray-Problem?
Dies ist ein klassisches Programmierproblem, bei dem es darum geht, die größte Summe zu finden zusammenhängendes Subarray innerhalb eines Arrays aus ganzen Zahlen. Die Lösung dieses Problems hat viele Anwendungen in Bereichen wie Finanzen, Datenanalyse und Signalverarbeitung. Der effizienteste Algorithmus zur Lösung dieses Problems ist der Kadane-Algorithmus.
Was ist der Kadane-Algorithmus?
Der Kadane-Algorithmus ist ein effizienter Ansatz zur Lösung des Maximum Contiguous Subarray-Problems. Der Algorithmus funktioniert, indem er local_maximum und global_maximum berechnet. Durch Iteration über das Array, beginnend von links, werden diese Variablen bei jedem Schritt aktualisiert, wobei das bisherige Maximum local_maximum das global_maximum ersetzt, wenn sein Wert größer ist. Sobald alle local_maximums berechnet wurden, ist das maximale zusammenhängende Subarray bekannt und gleich dem global_maximum.
Was ist der Brute-Force-Ansatz zur Lösung des Maximum-Subarray-Problems?
Der Brute-Force-Ansatz beinhaltet das Iterieren über alle möglichen Subarrays in einem Array und das Berechnen der Subarray-Summen. Das maximal zusammenhängende Subarray kann dann gefunden werden, aber der Prozess ist nicht sehr effizient, da jedes einzelne Subarray berechnet werden muss.
Welche Nachteile hat die Verwendung des Kadane-Algorithmus?
Obwohl der Algorithmus von Kadane einfach und effizient ist, kann er wirklich nur zur Lösung des Maximum-Subarray-Problems verwendet werden. Die Ausgabe, die es erzeugt, ist ebenfalls begrenzt, da es nur die Summe des maximalen Subarrays enthält. Über das Array selbst werden keine Informationen bereitgestellt, die für einige Anwendungen erforderlich sein können. Obwohl der Algorithmus schnell ist, ist die Lösung schließlich nicht in allen Fällen optimal.
Wie hoch ist die zeitliche Komplexität des Kadane-Algorithmus?
Die zeitliche Komplexität von Der Algorithmus von Kadane ist O(n).
Kann der Algorithmus von Kadane mit nicht zusammenhängenden Arrays verwendet werden?
Nein, der Algorithmus kann nicht mit verwendet werden nicht zusammenhängende Arrays.
Wie kann Kadanes Algorithmus modifiziert werden, um das Subarray mit der kleinsten Summe zu finden?
Wir können einfach die Funktion maxsize durch minsize ersetzen , und initialisieren Sie die Variablen auf unendlich statt auf Null.
Kann der Algorithmus von Kadane mit einem Array mit ausschließlich negativen Ganzzahlen verwendet werden?
Ja, der Algorithmus wird gibt in diesem Fall das Subarray mit der kleinsten negativen Summe zurück.