Beispiel: Maximum Subarray Problem
gegeben: Folge X von ganzen Zahlen der Länge n
gesucht: maximale Summe der Elemente einer zusammenhängenden Teilfolge
Naiver Algorithmus: int o,u; double summe, maxtsumme = 0; for (u = 0; u < N; u++) for (o = u; o < N; o++)
{ /* bestimme Summe der Elemente in Teilfolge X[u .. o] */ summe = 0; for (i = u; i <= o; i++) summe + = X[i]; maxtsumme = max(summe, maxtsumme); }