| Proseminar | |
| Programming Pearls | |
| Algorithm Design Techniques | |
| von Andreas Lenerz | |
Beispiel zu Algorithmus A1
Angenommen wir haben folgenden Eingabe:
| x[0] | x[1] | x[2] | x[3] | x[4] | x[5] | x[6] | x[7] |
| 31 | -41 | 59 | 26 | -53 | 58 | 97 | -23 |
| i | j | sum * | max_so_far |
| 0 | 0 | 31 | 31 |
| 0 | 1 | -10 | 31 |
| 0 | 2 | 49 | 49 |
| ... | |||
| 0 | 7 | 154 | 154 |
| 1 | 1 | -41 | 154 |
| 1 | 2 | 18 | 154 |
| ... | |||
| 2 | 6 | 187 | 187 |
| ... | |||
| 6 | 6 | 97 | 187 |
| 6 | 7 | 76 | 187 |
| 7 | 7 | -23 | 187 |
Ausgabe: max sum x[i..j] = 187
* Wert von sum nach Beendigung der inneren for.Schleife
Hier wird die Funktionsweise von A1 an dem Beispiel aus der Einleitung erläutert. Während in i und j die Funktionsweise der beiden äußeren Schleifen verdeutlicht wird, stellt die Variable sum das Ergebnis der innersten ( roten ) Schleife dar.
--> Zurück zu Algorithmus A1