首页 > 代码库 > clojure实现最长上升子序队列算法
clojure实现最长上升子序队列算法
4Clojure上的一道题:4Clojure 最长上升子序列算法
描述如下:
Given a vector of integers, find the longest consecutive sub-sequence of increasing numbers. If two sub-sequences have the same length, use the one that occurs first. An increasing sub-sequence must have a length of 2 or greater to qualify.
例:
[1 0 1 2 3 0 4 5]的最长上升子序列为 [0 1 2 3]
[5 6 1 3 2 7]的最长上升子序列为 [5 6]
(defn test [coll] ;使用map存放每个起始元素的上升队列,key无意义,仅用于标记不同的队列 (loop [flag 0 tmp-result {flag [(first coll)]} index 0] (if (< index (- (count coll) 1)) (let [current (nth coll index) next (nth coll (inc index))] (if (> next current) ;如果下一个元素大于当前元素,把下一个元素加入到当前元素的队列中,flag就是key,保持不变 (recur flag (assoc tmp-result flag (conj (tmp-result flag) next)) (inc index)) ;否则说明新的队列开始了,新建一个队列,key为flag+1,value为下一个元素 (recur (inc flag) (assoc tmp-result (inc flag) [next]) (inc index)))) ;得到结果之后筛选最长的队列 (let [tmp (vals tmp-result)] (loop [final (first tmp) s (next tmp)] (if (first s) (if (>= (count (first s)) (count final)) (recur (first s) (next s)) (recur final (next s))) ;队列长度至少为2 (if (> (count final) 1) final [])))))))
最终结果:
user=> (test [5 6 1 3 2 7]) [5 6] user=> (test [1 0 -1 3 0]) [-1 3] user=> (test [1 0 1 2 3 0 4 5]) [0 1 2 3]
clojure实现最长上升子序队列算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。