Noch besseres Verfahren: Scan-Line-Prinzip.
wir durchlaufen Positionen 1,...,n, merken uns jeweils die maximale Summe bismax im bisher inspizierten Anfangsstück sowie rechtes Randmaximum scanmax. Bei Vorrücken um 1 Position ist neue maximale Teilfolge entweder gleich der alten, oder sie enthält neues Randelement und ist dann das neue rechte Randmaximum. Neues rechtes Randmaximum ist scanmax + a, a Wert der nächsten Position, falls diese Summe positiv, sonst 0.
scanmax := 0; bismax := 0; for i := 1 to n do begin if scanmax + X[i] > 0 then scanmax := scanmax + X[i]
else scanmax := 0; bismax := max(scanmax, bismax) end