let lis arr =
  let n = Array.length arr in
  let dp = Array.make n 1 in
  for i = 1 to n - 1 do
    for j = 0 to i - 1 do
      if arr.(j) < arr.(i) && dp.(j) + 1 > dp.(i) then
        dp.(i) <- dp.(j) + 1
    done
  done;
  let best = ref 0 in
  for i = 0 to n - 1 do
    if dp.(i) > !best then best := dp.(i)
  done;
  !best

;;

lis [|10; 22; 9; 33; 21; 50; 41; 60; 80|]
