Einleitung

In den vergangenen Jahren ist die Börse als Möglichkeit der Geldanlage und dessen Vermehrung immer mehr in den Vordergrund getreten. Hierbei ist es für Statistiken sehr wichtig, daß man weiß, welche Aktie zu welchem Zeitpunkt ihren maximalen Gewinn abwarf oder über welchen Zeitraum ein maximaler Verlust eingetreten ist.
Um dieses Problem lösen zu können, bedient man sich in der heutigen Zeit eines Computers, der mit verschiedensten Algorithmen versucht, die ihm gestellten Aufgaben so effizient wie möglich korrekt zu lösen, wobei unter Effizienz die Komplexität in der Zeit und der zusätzlich zur Eingabe benötigte Speicherplatz verstanden werden kann.

Problem:
Array rationaler Zahlen x der Länge n ( vergleichbar mit den Gewinnen und Verlusten einer Aktie an aufeinanderfolgenden Tagen )

gesucht:
Indizes 0 <= i <= j < n , sodaß die Summe der Elemente von x[i] bis x[j] maximal wird !

Wie man im folgenden sehen wird, finden sich für dieses Problem die unterschiedlichsten Ansätze, die aber vor allem in der benötigten Zeit sehr große Unterschiede aufweisen werden.
In der Informatik ist es auch unter dem Namen

Das Max-Summen-Problem

bekannt.

Hierzu ein kurzes Beispiel:

Wenn hier x[0] bis x[7] die Gewinne bzw. Verluste einer Aktie an 8 aufeinanderfolgenden Tagen sind, so sieht man bereits nach kurzer Zeit, daß der maximale Gewinn eingetreten wäre, wenn man nach dem zweiten Tag gekauft und nach dem fünften wieder verkauft hätte.
sum x[2..6]=187
Zusätzlich fällt auf, daß auch negative Summanden ( wie hier x[4] ) mit in der maximalen Summe stehen können.

Ist eine Teilsumme sum x[k..l]<0 , so sagen wir, daß ihr Maximum max sum x[k..l] = 0

Für kleine Probleme mit wenigen Arrayelementen wie hier ist die gestellte Aufgabe leicht zu lösen. In der realen Anwendung kann man aber häufig von weit größeren Problemen ausgehen.
Die nun folgenden 5 Algorithmen beschäftigen sich mit der hier genannten Problemstellung, wobei die späteren Algorithmen versuchen durch Ausnutzung bestimmter Eigenschaften ihre Laufgeschwindigkeit weiter zu optimieren ...