所謂“最長不降子序列問題”，就是在一個給定的序列中尋找一個子序列{ai}滿足:
a1<=a2<=...<an
這個問題在一般教材上，往往會作為動態(tài)規(guī)劃的引例。
即使用如下的狀態(tài)轉(zhuǎn)移方程進行計算：
F[i]=max{F[j]}+1 aj<=ai
但是它的復雜度是O(n^2)的，對于稍大的規(guī)模便無法承受。
那么有沒有改進的方法呢？答案是肯定的。
----------------------------------------------------------------分割線------------------------------------------------------------------------------------------
我們維護一個數(shù)組C[i]，這里C[i]表示F值為i的最小數(shù)。
不難發(fā)現(xiàn) C[1]<=C[2]<=...<=C[n]
因此我們可以利用C[]通過二分查找確定F[j]的值。
----------------------------------------------------------------分割線------------------------------------------------------------------------------------------
實現(xiàn)如下：
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)的算法，它主要是利用了二分查找的方法對樸素的動態(tài)規(guī)劃進行加速、優(yōu)化，從而達到理想的效率。
轉(zhuǎn)自:http://fqq11679.blog.hexun.com/21632261_d.html