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.




 
>function %maxsubs (v,n) ...
$if n==1 then 
$  if (v[1]<0) then return {zeros(1,0),zeros(1,0)}
$  else return {v,v}; 
$  endif;
$endif;
${v1,v2}=%maxsubs(v[1:n-1],n-1);
$m1=sum(v1); m2=sum(v2); m3=m2+v[n]; 
$if m3>0 then v3=v2|v[n]; else v3=zeros(1,0); endif;
$if m3>m1 then return {v2|v[n],v3};
$else return {v1,v3};
$endif;
$endfunction
>function maxsubs (v) ...
${v1,v2}=%maxsubs(v,cols(v));
$return v1
$endfunction
>maxsubs([0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4])
 [ 0  1  2 ]
>maxsubs([-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1])
 [ 3  5  6  -2  -1  4 ]
>maxsubs([-1, -2, -3, -4, -5])
 Empty matrix of size 1x0
 