Specifikujte algoritmus pro nalezení maximální součtu v daném poli.
[1,2,3,4]
Jednoduchým řešením je projít pole a udržovat stopu maximálního součtu dosud nalezeného. To lze provést následujícím způsobem:
Projděte pole a pro každý prvek aktualizujte dosud nalezený maximální součet.

V libovolném bodě je dosud nalezený maximální součet buď samotný prvek, nebo součet předchozího maximálního součtu a aktuálního prvku.

Algoritmus lze tedy rekurzivně definovat následovně:
maxSum(i) = max(arr[i], maxSum(i-1)+arr[i])

Kde maxSum(i) představuje maximální součet s arr[i] jako posledním prvkem a arr[0...i] jako daným polem.