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.




PROC PrintArray(INT ARRAY a INT first,last)
  INT i
 
  Put('[)
  FOR i=first TO last
  DO
    IF i>first THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN
 
PROC Process(INT ARRAY a INT size)
  INT i,j,beg,end
  INT sum,best
 
  beg=0 end=-1 best=0
  FOR i=0 TO size-1
  DO
    sum=0
    FOR j=i TO size-1
    DO
      sum==+a(j)
      IF sum>best THEN
        best=sum
        beg=i
        end=j
      FI
    OD
  OD
 
  Print("Seq=") PrintArray(a,0,size-1)
  PrintF("Max sum=%i %ESubseq=",best)
  PrintArray(a,beg,end) PutE()
RETURN
 
PROC Main()
  INT ARRAY
    a(11)=[1 2 3 4 5 65528 65527 65516 40 25 65531],
    b(11)=[65535 65534 3 5 6 65534 65535 4 65532 2 65535],
    c(5)=[65535 65534 65533 65532 65531],
    d(0)=[]
 
  Process(a,11)
  Process(b,11)
  Process(c,5)
  Process(d,0)
RETURN