Algorithmus A1

Eingabe: Array rationaler Zahlen x der Länge n

Erläuterung:

max_so_far	die bisher größte gefundene Teilsumme. Da der Wert am Anfang null beträgt, wird somit zugleich sicher gestellt, daß kein negativer Wert für die maximale Summe herauskommt ( siehe Einleitung )
sum	die Variable, auf der in der innersten for-Schleife der Wert von sum x[i..j] bestimmt wird, indem sukzessiv alle x[k] mit i <= k <= j aufsummiert werden
max(x_1,x_2,..,x_n)	die Funktion, die das Maximum über die in der Klammer stehenden Werte x_1 .. x_n bezüglich des größer-Operators ">" zurückgibt.

Die innerste Schleife ( rot ) berechnet sum x[i..j] ( also die Summe eines Teilarrays ) und speichert diese auf der Variablen sum ab. Der nun folgende Schritt vergleicht das bisher gefundene Maximum auf der Variablen max_so_far mit der eben berechneten Summe bezüglich der Funktion max(-,-), welche bestimmt ob die Variable sum vielleicht das neue Maximum enthält und in diesem Fall die Variable max_so_far aktualisiert. Nun muß lediglich noch sicher gestellt werden, daß dieser Schritt für alle Teilsummen mit 0 <= i <= j < n bestimmt wird, da dann am Ende die Variable max_so_far die maximale Summe eines Teilarrays von x enthält. Gerade dafür sorgen die beiden äußeren for-Schleifen, die alle gültigen Kombinationen von i und j durchlaufen.

Laufzeit:
Man sieht leicht, daß der Algorithmus durch die 3 for-Schleifen, die maximal über n Werte laufen, eine Laufzeit von O( n³ ) besitzt.

Im Test ergab sich das folgenden Ergebnis:
Für 10.000 Werte benötigte A1 eine Zeit von: 39 min 23 sec 709 msec