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.




gss = (lst) :
   # Find discrete integral
   integral = (0)
   accum = 0
   lst each (n): accum = accum + n, integral append(accum).
   # Check integral[b + 1] - integral[a] for all 0 <= a <= b < N
   max = -1
   max_a = 0
   max_b = 0
   lst length times (b) :
      b times (a) :
         if (integral(b + 1) - integral(a) > max) :
            max = integral(b + 1) - integral(a)
            max_a = a
            max_b = b
         .
      .
   .
   # Print the results
   if (max >= 0) :
      (lst slice(max_a, max_b) join(" + "), " = ", max, "\n") join print
   .
   else :
      "No subsequence larger than 0\n" print
   .
.
 
gss((-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1))
gss((-1, -2, -3, -4, -5))
gss((7,-6, -8, 5, -2, -6, 7, 4, 8, -9, -3, 2, 6, -4, -6))