clojure - 如何过滤递增向量中递减的元素？

Question

例如

[1 2 3 40 7 30 31 32 41]

过滤后应该是

[1 2 3 30 31 32 41]

问题似乎不是很简单，因为我想最大化结果向量的大小，这样如果起始向量是

[1 2 3 40 30 31 32 41 29]

我更喜欢这个结果

[1 2 3 30 31 32 41]

不仅仅是

[1 2 3 29]

Answer 1

您的问题被称为 longest increasing subsequence .

通过 rosetta code :

(defn place [piles card]
  (let [[les gts] (->> piles (split-with #(<= (ffirst %) card)))
        newelem (cons card (->> les last first))
        modpile (cons newelem (first gts))]
    (concat les (cons modpile (rest gts)))))

(defn a-longest [cards]
  (let [piles (reduce place '() cards)]
    (->> piles last first reverse)))

(a-longest [1 2 3 40 30 31 32 41 29])
;; => (1 2 3 30 31 32 41)

如果您关心性能，可能可以优化为使用 transient 。