/* 

  Maximal non-segment sum in Picat.

  From  Alex Engelberg and Mark Engelberg "Solving Problems with Automata"
  https://www.youtube.com/watch?v=AEhULv4ruL4
  (around time 2:50, slide 5/40)
  """
  Given a sequence s of integers, find the maximum sum you can get by adding
  together a subsequence of numbers from s that do _not_ form a segment,
  i.e. a contigous block.
  """

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

*/

import cp.


main => go.

go ?=>
  N = 5,
  S = [-1,4,5,-3,-4],

  From :: 1..N,
  To   :: 1..N,
  
  Empty = new_list(N),
  Empty :: 0..1,

  Total #> 0,

  sum(Empty) #>= 1, % at least one empty in the range

  From #< To,
  % The empty element(s) must be in the range From..To
  foreach(I in 1..N)
    Empty[I] #= 1 #=> (From #< I #/\ To #> I)  
  end,

  Total #= sum([(I #>= From)*(I #=< To) * (S[I]*(Empty[I]#=0 )) :  I in 1..N]),

  Vars = Empty ++ S ++ [From,To],  
  solve($[max(Total),ff,split],Vars),

  println(s=S),
  println(total=Total),  
  println([from=From,to=To]),
  println(empty=Empty),
  println(selected=[S[I] : I in From..To, Empty[I] == 0]),
  nl,
  fail,

  nl.

go => true.

%
% Random instances
%
go2 ?=>
  nolog,
  N = 100,

  _ = random2(),
  S = [10 - (random() mod 20) : _ in 1..N],
  println(s=S),
  
  From :: 1..N,
  To   :: 1..N,
  
  Empty = new_list(N),
  Empty :: 0..1,

  Total #> 0,

  sum(Empty) #>= 1, % at least one empty 

  From #< To,
  % The empty element(s) must be in the range From..To
  foreach(I in 1..N)
    Empty[I] #= 1 #=> (From #< I #/\ To #> I)  
  end,

  Total #= sum([(I #>= From)*(I #=< To)*(S[I]*(Empty[I]#=0 )) :  I in 1..N]),

  Vars = Empty ++ [From,To],  
  solve($[max(Total),min,down],Vars),

  println(total=Total),  
  println([from=From,to=To]),
  println(empty=Empty),
  println(selected=[S[I] : I in From..To, Empty[I] == 0]),
  nl,
  fail,

  nl.

go2 => true.