所谓“最长不降子序列问题”，就是在一个给定的序列中寻找一个子序列{ai}满足:
a1<=a2<=...<an
这个问题在一般教材上，往往会作为动态规划的引例。
即使用如下的状态转移方程进行计算：
F[i]=max{F[j]}+1 aj<=ai
但是它的复杂度是O(n^2)的，对于稍大的规模便无法承受。
那么有没有改进的方法呢？答案是肯定的。
----------------------------------------------------------------分割线------------------------------------------------------------------------------------------
我们维护一个数组C[i]，这里C[i]表示F值为i的最小数。
不难发现 C[1]<=C[2]<=...<=C[n]
因此我们可以利用C[]通过二分查找确定F[j]的值。
----------------------------------------------------------------分割线------------------------------------------------------------------------------------------
实现如下：
const int N = 1001;
int a[N], C[N], f[N]; // f[i]用于记录a[0...i]的最大长度
int bsearch(const int *C, int size, const int &a)
{
int l=0, r=size-1;
while( l <= r )
{
int mid = (l+r)/2;
if( a > C[mid-1] && a <= C[mid] ) return mid; // >&&<= 换为: >= && <
else if( a < C[mid] ) r = mid-1;
else l = mid+1;
}
}
int LIS(const int *a, const int &n){
int i, j, size = 1;
C[0] = a[0]; f[0] = 1;
for( i=1; i < n; ++i ){
if( a[i] <= C[0] ) j = 0; // <= 换为: <
else if( a[i] >C[size-1] ) j = size++; // > 换为: >=
else j = bsearch(C, size, a[i]);
C[j] = a[i]; f[i] = j+1;
}
return size;
}
------------------------------------------------------------------分割线------------------------------------------------------------------------------------------
至此，我们了解了O(nlogn)的算法，它主要是利用了二分查找的方法对朴素的动态规划进行加速、优化，从而达到理想的效率。
转自:http://fqq11679.blog.hexun.com/21632261_d.html