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.




/* REXX ***************************************************************
* 10.08.2012 Walter Pachl Pascal algorithm -> Rexx -> NetRexx
**********************************************************************/
  s=' -1 -2  3  5  6 -2 -1  4 -4  2 -1'
  maxSum   = 0
  seqStart = 0
  seqEnd   = -1
  Loop i = 1 To s.words()
    seqSum = 0
    Loop j = i to s.words()
      seqSum = seqSum + s.word(j)
      if seqSum > maxSum then Do
        maxSum   = seqSum
        seqStart = i
        seqEnd   = j
        end
      end
    end
  Say 'Sequence:'
  Say s
  Say 'Subsequence with greatest sum: '
  If seqend<seqstart Then
    Say 'empty'
  Else Do
    ol='   '.copies(seqStart-1)
    Loop i = seqStart to seqEnd
      w=s.word(i)
      ol=ol||w.right(3)
      End
    Say ol
    Say 'Sum:' maxSum
    End