/*

  Greatest subsequential sum Picat.

  From http://rosettacode.org/wiki/Greatest_subsequential_sum
  """
  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 0; thus if all elements are negative, the 
  result must be the empty sequence. 
  """

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go =>
   nolog,
   LL = [[-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1],
         [-1,-2, 3],
         [-1,-2],
         [0],
         [],
         [144,  5, -8,  7, 15],
         [144,  -145, -8,  7, 15],
         [-144,  5, -8,  7, 15]
        ],

   foreach(L in LL)
     printf("%w: ", L),
     G = greatest_subsequential_sum1(L),
     println([G, sum(G)])
   end,
   nl,
   foreach(L in LL)
     printf("%w: ", L),
     G = greatest_subsequential_sum2(L),
     println([G, sum(G)])
   end,

   nl,
   foreach(L in LL)
     printf("%w: ", L),
     G = greatest_subsequential_sum3(L),
     println([G, sum(G)])
   end,

   nl.

% Imperative version
greatest_subsequential_sum1([]) = [] => true.
greatest_subsequential_sum1(A) = Seq => 
   Len = A.length,
   BeginMax = 0,
   EndMax = -1,
   MaxSum = 0,
   foreach(Begin in 1..Len)
      Sum = 0,
      foreach(End in Begin..Len)
         Sum := Sum + A[End],
         if Sum > MaxSum then
            MaxSum := Sum,
            BeginMax := Begin,
            EndMax := End
         end
      end
   end,
   Seq1 = [],
   if MaxSum > 0 then
     Seq1 := [A[I] : I in BeginMax..EndMax]
   else 
     Seq1 := []
   end,
   Seq = Seq1.


%
% alternative version: 
%  first build a map with all the combinations
%  then pick the one with greatest sum.
%
greatest_subsequential_sum2([]) = [] => true.
greatest_subsequential_sum2(A) = Seq =>
    P = allcomb(A),
    Total = max([Tot : Tot=_T in P]),
    Seq1 = [],
    if Total > 0 then
       [B,E] = P.get(Total),
       Seq1 := [A[I] : I in B..E]
    else 
      Seq1 := []
    end,
    Seq = Seq1.


allcomb(A) = Comb => 
   Len = A.length,
   Comb = new_map([(sum([A[I]:I in B..E])=([B,E])) : B in 1..Len, E in B..Len]).


%
% CP version
% Inspired by a MiniZinc model created by Claudio Cesar de Sá
%
greatest_subsequential_sum3([]) = [] => true.
greatest_subsequential_sum3(A) = Seq =>

   N = A.length,

   % decision variables
   Begin :: 1..N,
   End :: 1..N,

   X = new_list(N),
   X :: 0..1,

   TotalSum #= sum([X[I]*A[I] : I in 1..N]),
   SizeWindow #= sum(X),
   
   End #>= Begin,
   End - Begin #= SizeWindow -1,
   foreach(I in 1..N) 
      (Begin #=< I #/\ End #>= I) #<=> X[I] #= 1
   end,
   
   Vars = X ++ [Begin,End],
   solve($[ff,max(TotalSum)], Vars),

   if TotalSum > 0 then
     Seq = [A[I] : I in Begin..End]
   else 
     Seq = []
   end.