Maximale Teilsumme mit dem Kadane-Algorithmus
Kadanes Algorithmus entscheidet an jeder Position, ob eine neue Teilfolge beginnt oder die bisherige fortgesetzt wird.
Was ist Maximale Teilsumme mit dem Kadane-Algorithmus?
Kadanes Algorithmus entscheidet an jeder Position, ob eine neue Teilfolge beginnt oder die bisherige fortgesetzt wird.
Finde den zusammenhängenden Bereich mit der größten Summe.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Beispielcode
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]))Erwartete Ausgabe
6So funktioniert es
Eine einzige Iteration aktualisiert aktuelle und beste Summe. Dadurch entstehen O(n) Zeit und O(1) zusätzlicher Speicher.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.