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.




procedure main()
L1 := [-1,-2,3,5,6,-2,-1,4,-4,2,-1]     # sample list
L  := [-1,1,2,3,4,-11]|||L1             # prepend a local maximum into the mix
write(ximage(maxsubseq(L)))
end
 
link ximage      # to show lists
 
procedure maxsubseq(L)                    #: return the subsequence of L with maximum positive sum 
local i,maxglobal,maxglobalI,maxlocal,maxlocalI
 
maxglobal := maxlocal := 0                                           # global and local maxima
 
every i := 1 to *L do  {
   if (maxlocal := max(maxlocal +L[i],0)) > 0 then 
      if /maxlocalI then maxlocalI := [i,i] else maxlocalI[2] := i   # local maxima subscripts
   else maxlocalI := &null                                           # reset subsequence
   if maxglobal <:= maxlocal then                                    # global maxima
      maxglobalI := copy(maxlocalI)
   }
return L[(\maxglobalI)[1]:maxglobalI[2]] | []                        # return sub-sequence or empty list
end