求``最长递增子序列''

max-incseq.lisp

(defpackage :com.liutos.max-incseq
  (:use :cl)
  (:nicknames :max-incseq)
  (:documentation "计算一个序列的最长递增子序列"))

(in-package :max-incseq)

(defun max-incseq/aux (vec)
  "返回中间结果的数组，存储了到达各个数的最长递增子序列的长度。"
  (declare (type vector vec))
  (let ((aux (make-array (length vec) :initial-element 0)))
    (dotimes (i (length vec))
      (loop :for j :from i :to (1- (length vec))
	 :when (> (svref vec j) (svref vec i)) ;当前的数和起点的数谁比较大
	 :do (if (> (1+ (svref aux i)) (svref aux j))
		 (setf (svref aux j) (1+ (svref aux i))))))
    aux))

(defun max-posisition (vec)
  "在数值向量中找出最大值以及对应的下标"
  (let ((max (elt vec 0)) (p 0))
    (loop :for i :from 1 :to (1- (length vec))
       :when (> (svref vec i) max)
       :do (setf max (svref vec i)
		 p i))
    (values max p)))

(defun find-path (vec imd)
  "结合原来的数值序列和中间结果来推导出最长递增子序列"
  (multiple-value-bind (max pos)
      (max-posisition imd)
    (labels ((rec (acc idx len pre)		;acc是到目前为止得到的最长递增子序列的
					;后缀idx是目前所测试的对象在数组的下标
					;len是目前所要寻找的对象应该具有的序列长度
	       (if (zerop (svref imd idx))
		   (cons (svref vec idx) acc)
		   (if (and (< (svref vec idx) pre) ;当前遇到的数必须比后继节点小
			    (= len (svref imd idx))) ;并且长度刚好比后继节点对应的小一
		       (rec (cons (svref vec idx) acc)
			    (1- idx)
			    (1- len)
			    (svref vec idx))
		       (rec acc (1- idx) len pre)))))
      (rec '() pos max (1+ (svref vec pos))))))

(defun max-incseq (vec)
  "界面函数，方便使用而已。"
  (find-path vec (max-incseq/aux vec)))