31 lines
755 B
Text
31 lines
755 B
Text
greatest_subsequential_sum_cp([]) = [] => true.
|
|
greatest_subsequential_sum_cp(A) = Seq =>
|
|
N = A.length,
|
|
|
|
% decision variables: start and end indices
|
|
Begin :: 1..N,
|
|
End :: 1..N,
|
|
|
|
% 1 if the number is in the selected sequence, 0 if not.
|
|
X = new_list(N),
|
|
X :: 0..1,
|
|
|
|
% Get the total sum (to be maximized)
|
|
TotalSum #= sum([X[I]*A[I] : I in 1..N]),
|
|
SizeWindow #= sum(X),
|
|
|
|
% Calculate the windows of the greatest subsequential sum
|
|
End #>= Begin,
|
|
End - Begin #= SizeWindow -1,
|
|
foreach(I in 1..N)
|
|
(Begin #=< I #/\ End #>= I) #<=> X[I] #= 1
|
|
end,
|
|
|
|
Vars = X ++ [Begin,End],
|
|
solve($[inout,updown,max(TotalSum)], Vars),
|
|
|
|
if TotalSum > 0 then
|
|
Seq = [A[I] : I in Begin..End]
|
|
else
|
|
Seq = []
|
|
end.
|