21 lines
650 B
Common Lisp
21 lines
650 B
Common Lisp
(defun longest-increasing-subseq (list)
|
|
(let ((subseqs nil))
|
|
(dolist (item list)
|
|
(let ((longest-so-far (longest-list-in-lists (remove-if-not #'(lambda (l) (> item (car l))) subseqs))))
|
|
(push (cons item longest-so-far) subseqs)))
|
|
(reverse (longest-list-in-lists subseqs))))
|
|
|
|
(defun longest-list-in-lists (lists)
|
|
(let ((longest nil)
|
|
(longest-len 0))
|
|
(dolist (list lists)
|
|
(let ((len (length list)))
|
|
(when (> len longest-len)
|
|
(setf longest list
|
|
longest-len len))))
|
|
longest))
|
|
|
|
(dolist (l (list (list 3 2 6 4 5 1)
|
|
(list 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)))
|
|
(format t "~A~%" (longest-increasing-subseq l))))
|