4clojure #53 Longest Increasing Sub-Seq
#53 Longest Increasing Sub-Seq
(= (__ [1 0 1 2 3 0 4 5]) [0 1 2 3]) (= (__ [5 6 1 3 2 7]) [5 6]) (= (__ [2 3 3 4 5]) [3 4 5]) (= (__ [7 6 5 4]) [])
難しい。seqのなかで、1ずつ増加している箇所で、最長のものを求める。
シーケンス機能を利用して、まず1シーケンスから分割シーケンスに変換する。
あとはcount
でソートして最長のものを選択します。
ただし、この方法だと、解なしの場合でも長さ1のものが選択されてしまうので長さ1の場合は空ベクトルを返すように修正をいれました。
reduce
の第一引数由来の'((0))
始まりの分割シーケンスが答えの候補になる可能性があるが、4clojureの問題文からそうならないことが確認できたので特に対策はしていません。
WikiPediaに項目がありました。
Longest increasing subsequence
((fn [col] (let [ret (vec (reverse (first (sort-by count > (reduce #(if (= (inc (first (first %1))) %2) (cons (cons %2 (first %1)) (rest %1)) (cons (list %2) %1)) '((0)) col)))))] (if (= (count ret) 1) '[] ret))) [7 6 5 4])