list - OCaml 搜索最长递增子序列

Question

我试图在列表中找到最长的递增子序列。我有问题吗？有什么建议么 ？例如

[-5;6;7;8;-1;6;7;8;9;10;11;12]
The answer should be [-1;6;7;8;9;10;11;12]

Answer 1

以下代码片段回答了您的问题，恕我直言。

let longest l =
  let rec aux nbest best ncurr curr = function
    | [] -> List.rev best
    | hd :: tl when hd <= List.hd curr -> (* new sequence *)
        aux nbest best 1 [hd] tl
    | hd :: tl when nbest > ncurr ->
        aux nbest best (ncurr + 1) (hd :: curr) tl
    | hd :: tl ->
        aux (ncurr + 1) (hd :: curr) (ncurr + 1) (hd :: curr) tl
  in
  if l = [] then [] else aux 1 [List.hd l] 1 [List.hd l] (List.tl l)

let test = [-5; 6; 7; 8; -1; 6; 7; 8; 9; 10; 11; 12]

let () =
  List.iter (Printf.printf "%i ") (longest test)

请注意，它将返回第一个严格递增的序列，并且 nbest 和 ncurr 仅出于性能原因而存在。我看不到任何避免 List.rev 操作的方法。该函数是尾递归的。