Task

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 of   0;   thus if all elements are negative, the result must be the empty sequence.




 
(*
** This one is
** translated into ATS from the Ocaml entry
*)
 
(* ****** ****** *)
//
// How to compile:
// patscc -DATS_MEMALLOC_LIBC -o maxsubseq maxsubseq.dats
//
(* ****** ****** *)
//
#include
"share/atspre_staload.hats"
//
(* ****** ****** *)
 
typedef ints = List0(int)
 
(* ****** ****** *)
 
fun
maxsubseq
  (xs: ints): (int, ints) = let
//
fun
loop
(
  sum: int, seq: ints
, maxsum: int, maxseq: ints, xs: ints
) : (int, ints) =
(
case+ xs of
| nil () =>
  (
    maxsum
  , list_vt2t(list_reverse(maxseq))
  ) (* end of [nil] *)
| cons (x, xs) => let
    val sum = sum + x
    and seq = cons (x, seq)
  in
    if sum < 0
      then loop (0, nil, maxsum, maxseq, xs)
      else (
        if sum > maxsum
          then loop (sum, seq, sum, seq, xs)
          else loop (sum, seq, maxsum, maxseq, xs)
      ) (* end of [else] *)
  end // end of [cons]
)
//
in
  loop (0, nil, 0, nil, xs)
end // end of [maxsubseq]
 
implement
main0 () = () where
{
val
(maxsum
,maxseq) =
maxsubseq
(
  $list{int}(~1,~2,3,5,6,~2,~1,4,~4,2,~1)
)
//
val () = println! ("maxsum = ", maxsum)
val () = println! ("maxseq = ", maxseq)
//
} (* end of [main0] *)
 