CodeUtility
Mach dir das Coderleben leicht!
Python-Algorithmen

Maximum Subarray Sum with Kadane's Algorithm in Python

Find the run of numbers with the largest sum in one pass, even when the list has negative values.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel
Das lernst du
  • The best sum ending at each position
  • Starting fresh when the running sum hurts
  • O(n) time and O(1) memory
Im Python-Compiler ausführen →
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
-2
1
-3
4
-1
2
1
-5
4
4 - 1 + 2 + 1 = 6 is the largest sum of any contiguous run.

Extend the run or start again

Beim Problem des Teilarrays mit der größten Summe (maximum subarray) suchst du den Abschnitt aufeinanderfolgender Elemente mit der höchsten Summe in einer Liste mit positiven und negativen Zahlen. Der Kadane-Algorithmus löst das sehr effizient, indem er sich die beste Summe des Abschnitts merkt, der an der aktuellen Position endet.

Das Wichtigste

  1. current = max(value, current + value): keep the run only if it helps.
  2. best = max(best, current) remembers the best run so far.
  3. Start both from the first value so all-negative lists work.

Wann verwendet man das?

  • Problemlösendes Denken trainieren und Schritt für Schritt verstehen, wie ein Algorithmus arbeitet.
  • Den passenden Lösungsweg wählen, wenn viele Daten verarbeitet werden müssen oder das Programm schneller laufen soll.
  • Dich auf Prüfungen, Übungsaufgaben und Programmier-Vorstellungsgespräche vorbereiten.

Beispielcode

Code ausführen →
main.py
def maximum_subarray_sum(values):
    current = best = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Run-Button für dieses Beispiel erstellen

Ergebnis der Ausführung

6

Erklärung des Codes

Bei jedem Element wählt die Variable current zwischen zwei Möglichkeiten: einen neuen Abschnitt bei diesem Element beginnen oder den vorherigen Abschnitt mit current + value fortsetzen. Die Variable best speichert die größte bisher gesehene Summe. Bei den Beispieldaten liefert der Abschnitt [4, -1, 2, 1] die größte Summe, nämlich 6. Der Algorithmus läuft in O(n) und braucht nur O(1) Speicher.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungen zur Vertiefung

Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges