Maximale Teilsumme

Das Maximale-Teilsumme-Problem: Aus einem Array Zahlen soll man das jenige zusammenhängende Teilstück auswählen, dessen Summe am größten ist. Verschiedene Ansätze zur Lösung dieses Problems werden gezeigt. Am Ende steht ein Algorithmus, der geradezu unverschämt einfach anmutet, auf den man aber selbst kaum gekommen wäre: Der Algorithmus von Kadane. Ein schönes Beispiel dafür, wie nützlich das Prinzips des Dynamischen Programmierens ist. 00:00 - Intro 00:19 - Die Geschichte vom Schmuckhänder in Paris 05:44 - Maximale-Teilsumme-Problem 08:40 - Ansatz 1: Gier (Greedy Algorithmus) 11:28 - Ansatz 2: Rohe Gewalt (Brute Force) 16:34 - Ansatz 3: etwas weniger rohe Gewalt 19:13 - Ansatz 4: Teilen und Herrschen (Divide & Conquer) 35:35 - Ansatz 5: Memoisation 40:02 - Ansatz 6: Dynamisches Programmieren: Kadane's Algorithmus - Dynamisches Programmieren: https://youtu.be/LXtauLf4KpI - Teilen und Herrschen: https://youtu.be/jFZtAD8ePYk