Anwendung auf Maximum Subarray Problem:
Beobachtung: wenn man Folge in 2 Teile A und B teilt, so ist die gesuchte Teilfolge entweder in A, oder in B, oder in beiden.
Im letzten Fall sind die Randelemente in der gesuchten Teilfolge, und diese besteht aus 2 maximalen Teilstücken, die beim jeweiligen Rand beginnen (rechtes Randmaximum von A + linkes Randmaximum von B) .
Die Randmaxima von X[l], ..., X[r] kann man in linearer Zeit berechnen: lmax := 0; summe := 0; for i := l to r do begin summe := summe + X[i]; lmax := max(lmax, summe) end rmax analog.