/* 

  Maximum subarray problem in Picat.

  http://www.rosettacode.org/wiki/Maximum_subarray
  """
  Given an array of integers, find a subarray which maximizes the sum of its elements, 
  that is, the elements of no other single subarray add up to a value larger than this one. 
  An empty subarray is considered to have the sum 0; thus if all elements are negative, 
  the result must be the empty sequence.
  ...
  a1 = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1];
  Answer_ 
   Maximal subsequence: [3,5,6,-2,-1,4]
  (i.e. 3..8)

  auto a2 = [-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1];
  answer: Maximal subsequence: []
  """

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

*/

import sat.
% import cp.


main => go.

go ?=>
  nolog,
  % totSum = 6
  % [1,2,3] or [1,5]
  % L = [1, 2, 3, -100, 1, 5],

  % totSum = 15
  % [3,5,6,-2,-1,4]
  % L = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],

  % Answer: []
  % L = [-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1],

  % _ = random2(),
  L = [20 - random() mod 40 : _ in 1..100],
  
  println(l=L),

  maximum_subarray_cp(L,TotSum,From,To,Status),
  if Status == 1 then
    println(from=From),
    println(to=To),
    println(totSum=TotSum),
    println(L[From..To])
  else
    println([])
  end,

  nl.

go => true.

go2 ?=>
  nolog,
  % totSum = 6
  % [1,2,3] or [1,5]
  % L = [1, 2, 3, -100, 1, 5],

  % totSum = 15
  % [3,5,6,-2,-1,4]
  % L = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],

  % Answer: []
  % L = [-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1],

  % _ = random2(),
  L = [20 - random() mod 40 : _ in 1..1000],
  
  println(l=L),

  maximum_subarray_dp(L,Max),
  println(max=Max),
  nl.

go2 => true.

%
% CP approach: calculates the sum as well as the from..to indices.
% 
maximum_subarray_cp(L,TotSum,From,To,Status) =>
  N = L.len,

  % index of the sequence
  From :: 1..N,
  To :: 1..N,

  SSum = sum([abs(L[I]) : I in 1..N]),
  TotSum :: -SSum..SSum,

  Status :: 0..1,

  % get the indices and sum the subsequence
  sum([From #= I #/\ To #= J #/\
      TotSum #= sum([L[K] : K in I..J])
     : I in 1..N, J in I+1..N]) #>= 1, 

  TotSum #> 0 #<=> Status #= 1,

  Vars =  [From,To,Status],
  solve($[max(TotSum),constr,updown],Vars).

%
% Kadanes DP algorithm.
%
% From
% https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d
% Note: This just calculates the sum, not the indices.
%
maximum_subarray_dp(A,Max) =>
   N = A.len,
   LocalMax = 0,
   GlobalMax = -sum([abs(AA) : AA in A]), % -Infinity
   foreach(I in 1..N)
     LocalMax := max(A[I],A[I] + LocalMax),
     if LocalMax > GlobalMax then
       GlobalMax := LocalMax
     end
   end,
   Max = GlobalMax.