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