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.




*process source attributes xref;
 ss: Proc Options(Main);
 /* REXX ***************************************************************
 * 26.08.2013 Walter Pachl translated from REXX version 3
 **********************************************************************/
  Dcl HBOUND builtin;
  Dcl SYSPRINT Print;
  Dcl (I,J,LB,MAXSUM,SEQEND,SEQSTART,SEQSUM) Bin Fixed(15);
  Dcl s(11) Bin Fixed(15) Init(-1,-2,3,5,6,-2,-1,4,-4,2,-1);
  maxSum   = 0;
  seqStart = 0;
  seqEnd   = -1;
  do i = 1 To hbound(s);
    seqSum = 0;
    Do j = i to hbound(s);
      seqSum = seqSum + s(j);
      if seqSum > maxSum then Do;
        maxSum   = seqSum;
        seqStart = i;
        seqEnd   = j;
        end;
      end;
    end;
  Put Edit('Sequence:')(Skip,a);
  Put Edit('')(Skip,a);
  Do i=1 To hbound(s);
    Put Edit(s(i))(f(3));
    End;
  Put Edit('Subsequence with greatest sum:')(Skip,a);
  If seqend<seqstart Then
    Put Edit('empty')(Skip,a);
  Else Do;
    /*ol=copies('   ',seqStart-1)*/
    lb=(seqStart-1)*3;
    Put Edit(' ')(Skip,a(lb));
    Do i = seqStart to seqEnd;
      Put Edit(s(i))(f(3));
      End;
    Put Edit('Sum:',maxSum)(Skip,a,f(5));
    End;
 End;