23 lines
575 B
OCaml
23 lines
575 B
OCaml
|
let lis cmp list =
|
||
|
|
let pile_tops = Array.make (List.length list) [] in
|
||
|
|
let bsearch_piles x len =
|
||
|
|
let rec aux lo hi =
|
||
|
|
if lo > hi then
|
||
|
|
lo
|
||
|
|
else
|
||
|
|
let mid = (lo + hi) / 2 in
|
||
|
|
if cmp (List.hd pile_tops.(mid)) x < 0 then
|
||
|
|
aux (mid+1) hi
|
||
|
|
else
|
||
|
|
aux lo (mid-1)
|
||
|
|
in
|
||
|
|
aux 0 (len-1)
|
||
|
|
in
|
||
|
|
let f len x =
|
||
|
|
let i = bsearch_piles x len in
|
||
|
|
pile_tops.(i) <- x :: if i = 0 then [] else pile_tops.(i-1);
|
||
|
|
if i = len then len+1 else len
|
||
|
|
in
|
||
|
|
let len = List.fold_left f 0 list in
|
||
|
|
List.rev pile_tops.(len-1)
|