最长不下降子序列的O(n^2)算法和O(nlogn)算法
最長(zhǎng)不下降子序列(LIS:Longest Increasing Subsequence)
//用句通俗的話(huà)說(shuō)，我講的很通俗易懂~~
問(wèn)題描述：給出n個(gè)數(shù)，求出其最長(zhǎng)不下降子序列的長(zhǎng)度，比如n=5，5個(gè)數(shù)是{4,6,5,7,3}；其最長(zhǎng)下降子序列就是{4,6,7}，長(zhǎng)度為3。
一、簡(jiǎn)單的O（n^2)的算法
???????? 很容易想到用動(dòng)態(tài)規(guī)劃做。設(shè)lis[]用于保存第1~i元素元素中最長(zhǎng)不下降序列的長(zhǎng)度，則lis[i]=max(lis[j])+1,且num[i]>num[j],i>j。然后在lis[]中找到最大的一個(gè)值，時(shí)間復(fù)雜度是O(n^2)。
???????? 代碼實(shí)現(xiàn)：
????????? int Longest_Increasing(int num[],int n){
???????????????????? int lis[n],i,j;
??????????????????? for(i=0;i<n;i++){
?????????????????????????? lis[i]=1;
????????????????????????? for(j=0;j<i;j++)
???????????????????????????????? if(num[i]>num[j]&&lis[j]+1>lis[i])
???????????????????????????????????????????? lis[i]=lis[j]+1;
?????????????????????? }
?????????????????????? int maxn=0;
?????????????????????? for(i=0;i<n;i++) if(maxn<lis[i]) maxn=lis[i];
??????????????????????? return maxn;
?????????????? }
二、復(fù)雜點(diǎn)的O(nlogn)算法
?????????????? 概述：O(nlogn)的算法關(guān)鍵是它建立了一個(gè)數(shù)組b[]，b[i]表示長(zhǎng)度為i的不下降序列中結(jié)尾元素的最小值，用K表示數(shù)組目前的長(zhǎng)度，算法完成后K的值即為最長(zhǎng)不下降子序列的長(zhǎng)度。
?????????????? 具體點(diǎn)來(lái)講：
??????????????? 設(shè)當(dāng)前的以求出的長(zhǎng)度為K，則判斷a[i]和b[k]：
??????????????? 1.如果a[i]>=b[k]，即a[i]大于長(zhǎng)度為K的序列中的最后一個(gè)元素，這樣就可以使序列的長(zhǎng)度增加1，即K=K+1,然后現(xiàn)在的b[k]=a[i]；
?????????????????2.如果a[i]<b[k]，那么就在b[1]...b[k]中找到最大的j,使得b[j]<a[i],然后因?yàn)閎[j]<a[i]，所以a[i]大于長(zhǎng)度為j的序列的最后一個(gè)元素，那么就可以更新長(zhǎng)度為j+1的序列的最后一個(gè)元素，即b[j+1]=a[i]。
???????????????? 算法復(fù)雜度的分析：
?????????????? 因?yàn)楣灿衝個(gè)元素要進(jìn)行計(jì)算；每次計(jì)算又要查找n次，所以復(fù)雜度是O(n^2)，但是，注意到b[]數(shù)組里的元素的單調(diào)遞增的，所以我們可以用二分法，查找變成了logn次。這樣算法的復(fù)雜度就變成了O(nlogn)。具體算法實(shí)現(xiàn)請(qǐng)看代碼（7-13update：以前的blog用不了了，所以重新弄過(guò)了）。
?????????????? 下面這段代碼解決的是一道OI的題。
??????????????????????http://www.rqnoj.cn/Problem_Show.asp?PID=167
??????????? #include<iostream>
??????????? using namespace std;
??????????? long f[100001]={0},l=1,r,m,t=0,a;
??????????? inline void BinarySearch(){
?? ????????????????? while(l<=r){
?? ??????????????????????? m=(l+r)>>1;
?? ??????????????????????? if(f[m]==a){l=m;return;}
?? ??????????????????????? else
?? ???? ????????????????????????? if(f[m]>a)l=m+1;
?? ???? ???????????????????????? else r=m-1;
?? ????????????????? }
???????????? }
???????????? main(){
?? ??????????????????? long n;
?? ??????????????????? cin>>n;
?? ??????????????????? for(int i=1;i<=n;i++){
?? ???????????????????????? cin>>a;
?? ???????????????????????? if(a==0)continue;
?? ???????????????????????? l=1,r=t;
?? ???????????????????????? BinarySearch();
?? ??? ?? if(l<=t)f[l]=a;
?? ???????????????????????? else t++,f[t]=a;
?? ??????????????????? }
?? cout<<t;
?????????? }
//若仍然不能深刻理解可參考http://blog.sina.com.cn/s/reader_4ec7d3fc01000aet.html或跟我討論
總結(jié)
以上是生活随笔為你收集整理的最长不下降子序列的O(n^2)算法和O(nlogn)算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
