Algorithmus A5

Der Divide&Conquer Algorithmus A4 nutzt eine interessante Tatsache zur Bestimmung der Werte lmax und rmax, die man sich im folgenden weiter zu Nutzen machen kann. Er berechnet in der for-Schleife durch einmaliges Durchlaufen eines Teilarrays die maximale Summe ausgehend von einer festen Intervallgrenze, der Mitte des zu untersuchenden Intervalls.
Dabei kann man nicht nur die Tatsache aus Algorithmus A2, sondern auch eine etwas abgeänderte Art der Aufsummierung und des anschließenden Vergleichs in etwas anderer Form als neuen Algorithmus benutzen.
Vorüberlegung:
Als feste Intervallgrenze, in der dieser Algorithmus beginnt, sei das 0.te Element gegeben. Nun gibt es 2 Möglichkeiten:

• x[0] < 0
• x[0] >=0

Wenn x[0] < 0 gilt, dann kann doch die Summe mit x[0] ( x[0] + x[1] + ... ) nur kleiner sein als die Summe ohne x[0] ( x[1] + x[2] + x[3] + ... ).
Außerdem gilt, daß im anderen Falle eben genau diese Summe größer gleich der zweiten Summe ist.
Wenn also x[0] < 0 gilt, so kann x[0] niemals zu der maximalen Summe gehören, also kann das Verfahren mit x[1] anstatt mit x[0] erneut begonnen werden. Ist x[0] >= 0 , so ist im nächsten Schritt die Betrachtung von x[0] + x[1] möglich, anstatt von x[1] alleine.
Dies führt bei Fortführung des Verfahrens zu folgendem Algorithmus:

Eingabe: Array rationaler Zahlen x der Länge n

Erläuterung:

max_so_far	das bisherige Maximum irgend einer Teilsumme, am Ende steht in dieser Variablen der gesuchte Wert. Diese Variable hat also die gleiche Bedeutung wie in den anderen vorherigen Algorithmen auch
max_ending_here	Im Gegensatz zu max_so_far speichert diese Variable die maximale Endsumme. Ist die Schleife beim Wert i angekommen, dann beinhaltet max_ending_here den Wert, den auch die Schleife aus Algorithmus A4 liefern würde, wenn man beginnend bei i nach lmax suchen würde.

Das Komplizierteste an diesem Algorithmus ist die Nutzung der Variablen max_ending_here.

Gesucht ist gerade das j, sodaß sum x[j..i] >= sum x[k..i] , für alle k mit 0 <= k <= i .
Hierbei tritt dann gerade die oben genannte Tatsache in Kraft, daß nämlich für max_ending_here < 0 niemals gelten kann, daß max_ending_here + x[i] >= x[i] . Also kann das Verfahren auch mit x[i] als Startwert erneut beginnen ...

Laufzeit:
Da die einzige Schleife genau n mal durchlaufen wird, hat das Verfahren eine Laufzeit von O( n ) und ist somit in linearer Zeit lösbar.
Hierbei fällt ein weiterer bemerkenswerter Punkt auf:
Zur Bestimmung der richtigen Lösung wird jedes Arrayelement genau ein einziges Mal benutzt. Da sich das Verfahren anschaulich von "links nach rechts" über den Array bewegt, dabei jedes Element genau einmal betrachtet und aus diesen Informationen seine Entscheidungen trifft, nennt man es auch

Scanning Algorithmus
( Vgl. Scanline )

Im Test ergab sich das folgenden Ergebnis:
Für 10.000 Werte benötigte A2 eine Zeit von: 0 sec <1 msec
Für 100.000 Werte benötigte A2 eine Zeit von: 0 sec 20 msec

Frage: Ist es möglich einen Algorithmus zu entwerfen, der eine Laufzeit besser als O( n ) besitzt ?
Antwort: Da im Verlauf des Programms zur korrekten Bestimmung des Endergebnisses zumindest jeder Wert ein einziges Mal benutzt werden muß, kommt man niemals auf eine Laufzeit unter O( n ) für dieses Problem.