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.




gsss(list l, integer &start, &end, &maxsum)
{
    integer e, f, i, sum;
 
    end = f = maxsum = start = sum = 0;
    for (i, e in l) {
        sum += e;
        if (sum < 0) {
            sum = 0;
            f = i + 1;
        } elif (maxsum < sum) {
            maxsum = sum;
            end = i + 1;
            start = f;
        }
    }
}
 
main(void)
{
    integer start, end, sum;
    list l;
 
    l = list(-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1);
    gsss(l, start, end, sum);
    o_("Max sum ", sum, "\n");
    if (start < end) {
        l.ocall(o_, 1, start, end - 1, " ");
        o_newline();
    }
 
    0;
}