Proseminar
Programming Pearls
Algorithm Design Techniques
von Andreas Lenerz

Algorithmus A3

Eine andere Überlegung führt zu einer weiteren Möglichkeit, das gestellte Problem zu lösen:

Array x
x[0] x[1] x[2] ... x[n-2] x[n-1]
Array h
h[-1] h[0] h[1] h[2] ... h[n-2] h[n-1]

mit:
h[-1] = 0
h[i] = sum x[0..i]
Der Hilfsarray speichert auf seinem i-ten Element jeweils die Summe des Teilarrays x[0..i]. Er besitzt die Größe n+1, wobei das zusätzliche Element als x[-1] zur Verfügung steht ( Dies dient lediglich zu Anschauungszwecken und ist für eine Implementierung in dieser Form natürlich nicht geeignet )
Was kann man nun mit diesem Hilfsarray machen ?
Aber wenn man nun weiterhin erkennt, daß

sum x[i..j] = h[j] - h[i-1]

gilt, für 0 <= i <= j <= n , also die Summe der Teilarrays über die Hilfsunktion bestimmt werden kann, so kommt man zu folgendem Algorithmus.


Eingabe: Array rationaler Zahlen x der Länge n

Algorithmus A3:
cumarr[-1] = 0
for i = [0,n)
cumarr[i] = cumarr[i-1] + x[i]
max_so_far = 0
for i = [0,n)
for j = [i,n)
sum = cumarr[j] - cumarr[i-1]
max_so_far = max( max_so_far , sum )

Erläuterung:
cumarr[i]

die Bezeichnung des Hilfsarrays h von oben. cumarr kommt von "cumulated array". h[-1] = 0 wird benötigt, alls der rote Ausdruck mit i=0 aufgerufen wird.
Wie bereits in den vorigen Algorithmen auch wird die eigentliche Berechnung der Summen der Teilarrays in den rot markierten Zeilen durchgeführt. Auffällig ist jedoch die Vorbereitung ( grün ), die dem voraus geht. Zuerst wird der Hilfsarray cumarr erstellt, auf dem die die Teilsummen sum x[0..i] gespeichert werden. Mit ihm kann nun im Folgenden die eigentliche Berechnung durchgeführt werden.

cumarr[i-1]

x[0]+x[1]+x[2]+...+x[i-2]+x[i-1]
cumarr[j]

x[0]+x[1]+x[2]+...+x[i-2]+x[i-1] + x[i]+x[i+1]+...+x[j-1]+x[j]
cumarr[j] - cumarr[i-1]

x[i]+x[i+1]+x[i+2]+...+x[j-1]+x[j] = sum x[i..j]

Laufzeit:
Die Berechnung der Hilfsvariablen cumarr bzw. h kann in O( n ) geschehen. Die eigentliche Berechnung läuft weiterhin über 2 for-Schleifen, wie in A2 auch, was somit zu einer Laufzeit von O( n² ) führt.

Vorteile zu A1 Nachteile zu A1/A2
  • bessere Laufzeit
  • komplizierter, da Zusammenhang von oben ersichtlich sein muß
  • benötigt durch Nutzung des Hilfsarrays zusätzlich Speicherplatz

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

--> Weiter zu den Beispielen
--> Weiter zu Algorithmus A4
--> Zurück zum Hauptmenü