OCaml searchin增长最长的子序列

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操作的任何方式。该函数是尾递归的。