最长递减子序列

ArXoR

原帖由 yzc2002 于 5/9/06 14:10 发表
我得到的结果是扫描一遍序列，可以得到最长子序列，要拆分所有的子序列，最差的情况下（序列递增）要拆n次，所以是个O(n*n)的

O(n)扫描一遍就完成LIS了?
据我所知现在对于一般的LIS最好的结果就是O(nlgn)
楼主怎么实现的?

zouyuchong

给一个O(nlogn) 的

1、建立一个栈stack，清空。{stack[i]表示当前状态下，所有长度为i的子序中最后一个数的最小值}。

2、按先后顺序循环序列的每一个数，用操作3修改当前状态

3、如果这个数不小栈顶或栈为空就i<---++stack的长度，否则就用二分法找出一个最小的i使得stack[i]>这个数.将stack[i]更新为这个数。{可以用二分法是因为stack是有序的}

4、输出stack的长度。{最长不下子序长度}