https://www.cnblogs.com/sasuke-/p/5396843.html
今天我們要講的是最長上升子序列（LIS）。
【題目描述】
給定N個數，求這N個數的最長上升子序列的長度。
【樣例輸入】
7
2 5 3 4 1 7 6
【樣例輸出】
4
什么是最長上升子序列？ 就是給你一個序列，請你在其中求出一段不斷嚴格上升的部分，它不一定要連續(xù)。
就像這樣：2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的兩種選取方案。最長的長度是4.
那么，怎么求出它的最大上升子序列長度為4呢？這里介紹兩種方法，都是以動態(tài)規(guī)劃為基礎的。
首先，我們先介紹較慢（O（n2n2））的方法。我們記num為到這個數為止，最長上升子序列的長度。
這種方法就是每一次尋找“可以接下去的”，換句話說，設原序列為a，則
當aj<ai(j<i)ajnumi時，numi=numj+1numi=numj+1。
對于每一個數，他都是在“可以接下去”的中，從前面的最優(yōu)值+1轉移而來。
因此，這個算法是可以求出正確答案的。復雜度很明顯，外層i枚舉每個數，內層j枚舉目前i的最優(yōu)值，即O（n2n2）。
那么，有沒有更快的方法呢？當然有。這回要用到二分。
我們回想一下，在上面O（n2n2）的程序中，哪些地方看起來比較費時？
沒錯，就是內層用于更新i的循環(huán)。因為每一次他都要查找一遍，效率并不高。
回到題目，我們發(fā)現，他只要我們求長度，所以？
我們可以模擬一個棧。
所以每遇到一個比棧頂元素大的數，就放進棧里，遇到比棧頂元素小的就二分查找前邊的元素，找到一個“最應該被換掉的元素”，用新數去更新前邊的元素。
這個算法不難證明也是正確的。因為前面每一次的枚舉都換成了二分，內層的復雜度從nn降到了log2log2，外層不變。所以總的復雜度是O(nlog2nnlog2n)。
接下來，我先給出樸素算法的代碼。
#includeconstintMAX=1001;int a[MAX];intlis(int x)
{
? ? int num[MAX];
? ? for(inti=0;i
? ? {
? ? ? ? num[i]=1;
? ? ? ? for(intj=0;j
? ? ? ? {
? ? ? ? ? ? if(a[j]num[i])
? ? ? ? ? ? ? ? ? num[i]=num[j]+1;
? ? ? ? }
? ? }
? ? intmaxx=0;
? ? for(inti=0;i
? ? ? ? if(maxx
? ? ? ? ? ? maxx=num[i];
? ? return maxx;
}int main()
{
? ? int n;
? ? scanf("%d",&n);
? ? for(inti=0;i
? ? ? ? scanf("%d",&a[i]);
? ? return!printf("%d\n",lis(n));
}
這個則是二分算法的代碼：
#include#includeconstintMAXN=200001;int a[MAXN];int d[MAXN];int main()
{
? ? int n;
? ? scanf("%d",&n);
? ? for(inti=1;i<=n;i++)
? ? ? ? scanf("%d",&a[i]);
? ? d[1]=a[1];
? ? intlen=1;
? ? for(inti=2;i<=n;i++)
? ? {
? ? ? ? if(a[i]>d[len])
? ? ? ? ? ? d[++len]=a[i];
? ? ? ? else? ? ? ? {
? ? ? ? ? ? intj=std::lower_bound(d+1,d+len+1,a[i])-d;
? ? ? ? ? ? d[j]=a[i];
? ? ? ? }
? ? }
? ? printf("%d\n",len);? ?
? ? return0;
}
類似的，我們可以通過二分查找中改變“上確界”和“下確界”，以及符號（“<”和“<=”或“>”、“>=”等），求出最長不下降、不上升、嚴格下降子序列等問題。
希望對大家有幫助。滿意請點贊！
