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.




 
/*Special ordered set of type N
 
  Nigel_Galloway
  January 26th, 2012
*/
 
param Lmax;
param Lmin;
set SOS;
param Sx{SOS};
var db{Lmin..Lmax,SOS}, binary;
 
maximize s : sum{q in (Lmin..Lmax),t in (0..q-1), z in SOS: z > (q-1)} Sx[z-t]*db[q,z];
sos1 : sum{t in (Lmin..Lmax),z in SOS: z > (t-1)} db[t,z] = 1;
solve;
 
for{t in (Lmin..Lmax),z in SOS: db[t,z] == 1} {
  printf "\nA sub-sequence of length %d sums to %f:\n", t,s;
  printf{q in (z-t+1)..z} "  %f", Sx[q];
}
printf "\n\n";
 
data;
param Lmin := 1;
param Lmax := 6;
param:
SOS:  Sx :=
 1     7
 2     4 
 3   -11 
 4     6
 5     3
 6     1
;
 
end;
 