在给定的数组中找出各元素之和在所有子集中最大的子数组

maxSubseq.ml

let maxSubseq seq =
  let aux = Array.create (Array.length seq) 0
  and len = Array.length seq
  and iStart = ref 0
  and iEnd = ref 0
  and max = ref 0
  in
  begin
    aux.(0) <- seq.(0);
    max := seq.(0);
    for i = 1 to len - 1 do
      if aux.(i - 1) + seq.(i) > seq.(i)
      then aux.(i) <- aux.(i - 1) + seq.(i)
      else aux.(i) <- seq.(i);
      if aux.(i) > !max
      then
	begin
	  max := aux.(i);
	  if !iEnd = i - 1
	  then iEnd := !iEnd + 1
	  else (iStart := i; iEnd := i)
	end;
    done;
  end;
  Array.sub seq !iStart (!iEnd - !iStart + 1)