今天我們要講的是最長(zhǎng)上升子序列（LIS）。
【題目描述】
給定N個(gè)數(shù)，求這N個(gè)數(shù)的最長(zhǎng)上升子序列的長(zhǎng)度。
【樣例輸入】 　　　　 【樣例輸出】
7 ? 　　 ? ? ? ? ? ?　　　　4
2 5 3 4 1 7 6

那么什么是最長(zhǎng)上升子序列呢？
就是給你一個(gè)序列，請(qǐng)你在其中求出一段不斷嚴(yán)格上升的部分，它不一定是要連續(xù)的。
就像這樣：2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的兩種選取方案，這個(gè)數(shù)列的最長(zhǎng)長(zhǎng)度是4.

那么，怎么求出它的最大上升子序列長(zhǎng)度為4呢？這里介紹兩種方法，都是以動(dòng)態(tài)規(guī)劃為基礎(chǔ)的。

首先，我們先介紹較慢（O（n2））的方法。我們記num為到這個(gè)數(shù)為止時(shí)的最長(zhǎng)上升子序列的長(zhǎng)度。

?

這種方法就是每一次尋找“可以接下去的”，換句話(huà)說(shuō)，設(shè)原序列為a，則
　　當(dāng)aj<ai(j<i)且numj+1>numi時(shí)，numi=numj+1。
對(duì)于每一個(gè)數(shù)，他都是在“可以接下去”的中，從前面的最優(yōu)值+1轉(zhuǎn)移而來(lái)。
因此，這個(gè)算法是可以求出正確答案的。

復(fù)雜度很明顯，外層i枚舉每個(gè)數(shù)，內(nèi)層j枚舉目前i的最優(yōu)值，即O（n2）。

那么，有沒(méi)有更快的方法呢？當(dāng)然有。這回要用到二分。
我們回想一下，在上面O（n2）的程序中，哪些地方看起來(lái)比較費(fèi)時(shí)？
沒(méi)錯(cuò)，就是內(nèi)層用于更新i的循環(huán)。因?yàn)槊恳淮嗡家檎乙槐?#xff0c;效率并不高。
回到題目，我們發(fā)現(xiàn)，他只要我們求長(zhǎng)度，所以……？
我們可以模擬一個(gè)棧。
每遇到一個(gè)比棧頂元素大的數(shù)，就放進(jìn)棧里，遇到比棧頂元素小的就二分查找前邊的元素，找到一個(gè)“最應(yīng)該被換掉的元素”，用新數(shù)去更新前邊的元素。
這個(gè)算法不難證明也是正確的。因?yàn)榍懊婷恳淮蔚拿杜e都換成了二分，內(nèi)層的復(fù)雜度從n降到了log2，外層不變。所以總的復(fù)雜度是O(nlog2n)。

接下來(lái)，我先給出樸素算法的代碼。

1 #include<cstdio> 2 const int MAX=1001; 3 int a[MAX]; 4 int lis(int x) 5 { 6 int num[MAX]; 7 for(int i=0;i<x;i++) 8 { 9 num[i]=1; 10 for(int j=0;j<i;j++) 11 { 12 if(a[j]<a[i]&&num[j]+1>num[i]) 13 num[i]=num[j]+1; 14 } 15 } 16 int maxx=0; 17 for(int i=0;i<x;i++) 18 if(maxx<num[i]) 19 maxx=num[i]; 20 return maxx; 21 } 22 int main() 23 { 24 int n; 25 scanf("%d",&n); 26 for(int i=0;i<n;i++) 27 scanf("%d",&a[i]); 28 return !printf("%d\n",lis(n)); 29 }

這個(gè)則是二分算法的代碼：

1 #include<cstdio> 2 #include<algorithm> 3 const int MAXN=200001; 4 5 int a[MAXN]; 6 int d[MAXN]; 7 8 int main() 9 { 10　　int n; 11　　scanf("%d",&n); 12　　for(int i=1;i<=n;i++) 13 　　 scanf("%d",&a[i]); 14　　d[1]=a[1]; 15　　int len=1; 16　　for(int i=2;i<=n;i++) 17　　{ 18　　　　if(a[i]>d[len]) 19　　　　　　d[++len]=a[i]; 20　　　　else 21　　　　　　{ 22　　　　　　　　int j=std::lower_bound(d+1,d+len+1,a[i])-d; 23　　　　　　　　d[j]=a[i]; 24　　　　　　} 25　　} 26　　printf("%d\n",len); 27　　return 0; 28}

類(lèi)似的，我們可以通過(guò)二分查找中改變“上確界”和“下確界”，以及符號(hào)（“<”和“<=”或“>”、“>=”等），求出最長(zhǎng)不下降、不上升、嚴(yán)格下降子序列等問(wèn)題。

?

由于作者也正在學(xué)習(xí)中，這篇文章只是借用別人的文章并加上自己的理解。

原文：http://www.cnblogs.com/frankchenfu/

轉(zhuǎn)載于:https://www.cnblogs.com/zhengyongle506/p/10554208.html

總結(jié)

以上是生活随笔為你收集整理的动态规划算法——最长上升子序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。