Task

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one.



An empty subsequence is considered to have the sum of   0;   thus if all elements are negative, the result must be the empty sequence.




include c:\cxpl\codes;
int Array, Size, Sum, Best, I, Lo, Hi, BLo, BHi;
 
[Array:= [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1];
Size:= 11;
Best:= -100000;
for Lo:= 0 to Size-1 do
    for Hi:= Lo to Size-1 do
        [Sum:= 0;
        for I:= Lo to Hi do
                Sum:= Sum + Array(I);
        if Sum > Best then
                [Best:= Sum;  BLo:= Lo;  BHi:= Hi];
        ];
Text(0, "Sequence = ");
for I:= 0 to Size-1 do
        [IntOut(0, Array(I)); Text(0, " ")];
CrLf(0);
Text(0, "Greatest = ");
for I:= BLo to BHi do
        [IntOut(0, Array(I)); Text(0, " ")];
CrLf(0);
Text(0, "Sum = ");  IntOut(0, Best);  CrLf(0);
]