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 "seed7_05.s7i";
 
const func array integer: maxSubseq (in array integer: sequence) is func
  result
    var array integer: maxSequence is 0 times 0;
  local
    var integer: number is 0;
    var integer: index is 0;
    var integer: currentSum is 0;
    var integer: currentStart is 1;
    var integer: maxSum is 0;
    var integer: startPos is 0;
    var integer: endPos is 0;
  begin
    for number key index range sequence do
      currentSum +:= number;
      if currentSum < 0 then
        currentStart := succ(index);
        currentSum := 0;
      elsif currentSum > maxSum then
        maxSum := currentSum;
        startPos := currentStart;
        endPos := index;
      end if;
    end for;
    if startPos <= endPos and startPos >= 1 and endPos >= 1 then
      maxSequence := sequence[startPos .. endPos];
    end if;
  end func;
 
const proc: main is func
  local
    const array integer: a1 is [] (-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1);
    const array integer: a2 is [] (-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1);
    var integer: number is 0;
  begin
    write("Maximal subsequence:");
    for number range maxSubseq(a1) do
      write(" " <& number);
    end for;
    writeln;
    write("Maximal subsequence:");
    for number range maxSubseq(a2) do
      write(" " <& number);
    end for;
    writeln;
  end func;