Module Maxseq

Module Maxseq

let rec max_praefix l = (* determine the ``maximal'' prefix *)
   match l with
     [ ] ® ([ ],0)
   | x::tl ®
       let (l', m) = (max_praefix tl)
       in
       if (x+m) ³ 0
       then (x::l', x+m)
       else ( [ ], 0)

let max_postfix l = (* analogoulsy for postfix *)
   let (postfix, m) = (max_praefix (List.rev l))
   in (List.rev postfix, m)

let rec step (l: (int list × int list × int) list) =
(* sub list max seq max *)
   match l with
     [ ] ® [ ]
   | [e] ® [e]
   | (ll, seq_l, max_l) :: (lr, seq_r, max_r) :: tl ®
       let (post, max_1) = max_postfix ll
       and (prae, max_2) = max_praefix lr
       in
       match ( max_1+max_2£ max_l, max_l £ max_r, max_r £ max_1+max_2)
       with
         (true, true, _ ) ® (ll@lr, seq_r, max_r) :: step tl
       | (true, _ , true) ® (ll@lr, seq_l, max_l) :: step tl
       | ( _ , true, true) ® (ll@lr, post@prae, max_1+max_2) :: step tl
       | (true, false,false) ® (ll@lr, seq_l, max_l) :: step tl
       | (false,true, false) ® (ll@lr, seq_r, max_r) :: step tl
       | (false,false,true) ® (ll@lr, post@prae, max_1+max_2) :: step tl
       | _ ® raise ( Failure "Cannot happen")

let rec steps (l: (int list × int list × int) list) =
   match l with
     [ ] ® ([ ],[ ],0)
   | [l1] ® l1
   | _ ® steps (step l)

let rec explode_seq (l : int list) =
   match l with
     [ ] ® [ ]
   | x::tl ®
       if x³0
       then ([x], [x], x) :: explode_seq tl
       else ([x], [ ], 0) :: explode_seq tl

let maxseq (l : int list) =
   let (_,s,_) = steps(explode_seq l) in s
January 31, 2002