| Proseminar | |
| Programming Pearls | |
| Algorithm Design Techniques | |
| von Andreas Lenerz | |
Beispiel zu Algorithmus A3
Wieder einmal benutzen wir die folgenden Eingabe:
| i | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| x[i] | 31 | -41 | 59 | 26 | -53 | 58 | 97 | -23 | |
| cumarr[i] | 0 | 31 | -10 | 49 | 75 | 22 | 80 | 177 | 154 |
Hier sieht man die Belegung des Hilfsarrays.
h[-1] = 0
h[i] = sum x[0..i]
| 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 |
* sum = cumarr[j] - cumarr[i-1]
--> Zurück zu Algorithmus A3