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.




func maxsubseq(*a) {
    var (start, end, sum, maxsum) = (-1, -1, 0, 0);
    a.each_kv { |i, x|
        sum += x;
        if (maxsum < sum) {
            maxsum = sum;
            end = i;
        }
        elsif (sum < 0) {
            sum = 0;
            start = i;
        }
    };
    a.ft(start+1, end);
}
 
say maxsubseq(-1, -2,  3,  5,  6, -2, -1,  4, -4,  2, -1);
say maxsubseq(-2, -2, -1,  3,  5,  6, -1,  4, -4,  2, -1);
say maxsubseq(-2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1);