Proseminar
Programming Pearls
Algorithm Design Techniques
von Andreas Lenerz

Beispiel zu Algorithmus A4

Betrachten wir das folgende Beispiel:

0 1 2 3 4 5 6 7
31 -41 59 26 -53 58 97 -23

0 1 2 3
31 -41 59 26
4 5 6 7
-53 58 97 -23

0 1
31 -41
2 3
59 26
4 5
-53 58
6 7
97 -23

0
31
1
-41
2
59
3
26
4
-53
5
58
6
97
7
-23

Nachdem durch Rekursion viele kleine Teilarrays enstanden sind, bricht diese ab und versucht nun durch Kombination der vorigen Ergebnisse das Maximum zu bestimmen.
Gut zu erkennen ist hier bei der ersten Teilung, daß das spätere Maximum geteilt wird ( grün ). In den beiden for-Schleifen des Ausgangsarrays findet man als lmax gerade sum x[2..3] und als rmax sum x[4..6] , die dann später beim Zusammenfügen wieder zu einem ( also sum x[2..6] ) vereint werden.
Die blau markierten Elemente unten links beispielsweise liefern als Ergebnis folgendes zurück:
return max( 0 , 31 ) = 31 ( in der if-Schleife )
return max( 0 , -41 )= 0 ( in der if-Schleife )
Damit ergibt sich in der Ebene darüber:
return max( 31 + 0 , 0 , 31 ) = 31

--> Zurück zu Algorithmus A4
--> Weiter zu Algorithmus A5
--> Zurück zum Hauptmenü