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操作的任何方式。該函數是尾遞歸的。