轉(zhuǎn)自：http://www.slyar.com/blog/poj-2533-cpp.html

POJ 2533 Longest Ordered Subsequence

屬于簡(jiǎn)單的經(jīng)典的DP，求最長(zhǎng)上升子序列(LIS)。先研究了O(n^2)的思路。

令A(yù)[i]表示輸入第i個(gè)元素，D[i]表示從A[1]到A[i]中以A[i]結(jié)尾的最長(zhǎng)子序列長(zhǎng)度。對(duì)于任意的0 <? j <= i-1，如果A(j) < A(i)，則A(i)可以接在A(yíng)(j)后面形成一個(gè)以A(i)結(jié)尾的新的最長(zhǎng)上升子序列。對(duì)于所有的 0 <? j <= i-1，我們需要找出其中的最大值。

DP狀態(tài)轉(zhuǎn)移方程:

D[i] = max{1, D[j] + 1} (j = 1, 2, 3, ..., i-1 且 A[j] < A[i])

解釋一下這個(gè)方程，i， j在范圍內(nèi):

如果 A[j] < A[i] ，則D[i] = D[j] + 1

如果 A[j] >= A[i] ，則D[i] = 1

#include <iostream> #define SIZE 1001using namespace std;int main() {int i, j, n, max;/* a[i]表示輸入第i個(gè)元素 */int a[SIZE];/* d[i]表示以a[i]結(jié)尾的最長(zhǎng)子序列長(zhǎng)度 */int d[SIZE];cin >> n;for (i = 1; i <= n; i++){cin >> a[i];}max = 0;for (i = 1; i <= n; i++){d[i] = 1;for (j = 1; j <= i - 1; j++){if (a[j] < a[i] && d[i] < d[j] + 1){d[i] = d[j] + 1;}}/* 記錄最長(zhǎng)子序列 */if (d[i] > max) max = d[i];}cout << max << endl;//system("pause");return 0; }

還有一個(gè)O(nlogn)的算法：

這個(gè)算法其實(shí)已經(jīng)不是DP了，有點(diǎn)像貪心。至于復(fù)雜度降低其實(shí)是因?yàn)檫@個(gè)算法里面用到了二分搜索。本來(lái)有N個(gè)數(shù)要處理是O(n)，每次計(jì)算要查找N次還是O(n)，一共就是O(n^2)；現(xiàn)在搜索換成了O(logn)的二分搜索，總的復(fù)雜度就變?yōu)镺(nlogn)了。

這個(gè)算法的具體操作如下(by RyanWang):

開(kāi)一個(gè)棧，每次取棧頂元素top和讀到的元素temp做比較，如果temp > top 則將temp入棧；如果temp < top則二分查找棧中的比temp大的第1個(gè)數(shù)，并用temp替換它。 最長(zhǎng)序列長(zhǎng)度即為棧的大小top。

這也是很好理解的，對(duì)于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替換Stack[y]，此時(shí)的最長(zhǎng)序列長(zhǎng)度沒(méi)有改變但序列Q的''潛力''增大了。

舉例：原序列為1，5，8，3，6，7

棧為1，5，8，此時(shí)讀到3，用3替換5，得到1，3，8； 再讀6，用6替換8，得到1，3，6；再讀7，得到最終棧為1，3，6，7。最長(zhǎng)遞增子序列為長(zhǎng)度4。但是這個(gè)代碼只能求出長(zhǎng)度，并不能求出具體的序列

雙端LIS：http://blog.csdn.net/v_JULY_v/article/details/6419466

也是基于這個(gè)算法，但是記錄了每個(gè)i對(duì)應(yīng)的最長(zhǎng)上升序列的長(zhǎng)度

用該算法完成POJ2533的具體代碼如下:

#include <iostream> #define SIZE 1001using namespace std;int main() {int i, j, n, top, temp;int stack[SIZE];cin >> n;top = 0;/* 第一個(gè)元素可能為0 */stack[0] = -1;for (i = 0; i < n; i++){cin >> temp;/* 比棧頂元素大數(shù)就入棧 */if (temp > stack[top]){stack[++top] = temp;}else{int low = 1, high = top;int mid;/* 二分檢索棧中比temp大的第一個(gè)數(shù) */while(low <= high){mid = (low + high) / 2;if (temp > stack[mid])//{low = mid + 1;}else{high = mid - 1;}}/* 用temp替換 */stack[low] = temp;}}/* 最長(zhǎng)序列數(shù)就是棧的大小 */cout << top << endl;//system("pause");return 0; }


總體思想就是從左到右掃描，保證棧的長(zhǎng)度是增長(zhǎng)的，具體原因，不太理解
算法3 O(nlogn) 轉(zhuǎn)自：http://www.cppblog.com/superKiki/archive/2011/04/06/143500.html
設(shè) A[t]表示序列中的第t個(gè)數(shù)，F[t]表示從1到t這一段中以t結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度，初始時(shí)設(shè)F [t] = 0(t = 1, 2, ..., len(A))。則有動(dòng)態(tài)規(guī)劃方程：F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。?

現(xiàn)在，我們仔細(xì)考慮計(jì)算F[t]時(shí)的情況。假設(shè)有兩個(gè)元素A[x]和A[y]，滿(mǎn)足?
(1)x < y < t?
(2)A[x] < A[y] < A[t]?
(3)F[x] = F[y]?
此時(shí)，選擇F[x]和選擇F[y]都可以得到同樣的F[t]值，那么，在最長(zhǎng)上升子序列的這個(gè)位置中，應(yīng)該選擇A[x]還是應(yīng)該選擇A[y]呢？?
很明顯，選擇A[x]比選擇A[y]要好。因?yàn)橛捎跅l件(2)，在A(yíng)[x+1] ... A[t-1]這一段中，如果存在A(yíng)[z]，A[x] < A[z] < a[y]，則與選擇A[y]相比，將會(huì)得到更長(zhǎng)的上升子序列。?
再根據(jù)條件(3)，我們會(huì)得到一個(gè)啟示：根據(jù)F[]的值進(jìn)行分類(lèi)。對(duì)于F[]的每一個(gè)取值k，我們只需要保留滿(mǎn)足F[t] = k的所有A[t]中的最小值。設(shè)D[k]記錄這個(gè)值，即D[k] = min{A[t]} (F[t] = k)。?

注意到D[]的兩個(gè)特點(diǎn)：?
(1)　D[k]的值是在整個(gè)計(jì)算過(guò)程中是單調(diào)不上升的。?
(2)　D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。?

利 用D[]，我們可以得到另外一種計(jì)算最長(zhǎng)上升子序列長(zhǎng)度的方法。設(shè)當(dāng)前已經(jīng)求出的最長(zhǎng)上升子序列長(zhǎng)度為len。先判斷A[t]與D[len]。若A [t] > D[len]，則將A[t]接在D[len]后將得到一個(gè)更長(zhǎng)的上升子序列，len = len + 1， D[len] = A [t]；否則，在D[1]..D[len]中，找到最大的j，滿(mǎn)足D[j] < A[t]。令k = j + 1，則有A [t] <= D[k]，將A[t]接在D[j]后將得到一個(gè)更長(zhǎng)的上升子序列，更新D[k] = A[t]。最后，len即為所要求的最長(zhǎng)上 升子序列的長(zhǎng)度。?

在 上述算法中，若使用樸素的順序查找在D[1]..D[len]查找，由于共有O(n)個(gè)元素需要計(jì)算，每次計(jì)算時(shí)的復(fù)雜度是O(n)，則整個(gè)算法的 時(shí)間復(fù)雜度為O(n^2)，與原來(lái)的算法相比沒(méi)有任何進(jìn)步。但是由于D[]的特點(diǎn)(2)，我們?cè)贒[]中查找時(shí)，可以使用二分查找高效地完成，則整個(gè)算法 的時(shí)間復(fù)雜度下降為O(nlogn)，有了非常顯著的提高。需要注意的是，D[]在算法結(jié)束后記錄的并不是一個(gè)符合題意的最長(zhǎng)上升子序列！

#include?<iostream>
using?namespace?std;
int?find(int?*a,int?len,int?n)//若返回值為x,則a[x]>=n>a[x-1]
{
????int?left=0,right=len,mid=(left+right)/2;
????while(left<=right)
????{
????????if(n>a[mid])?left=mid+1;
????????else?if(n<a[mid])?right=mid-1;
????????else?return?mid;
????????mid=(left+right)/2;
????}
????return?left;??
}
void?fill(int?*a,int?n)
{
????for(int?i=0;i<=n;i++)
????????a[i]=1000;
}
int?main()
{
????int?max,i,j,n,a[100],b[100],c[100];
????while(cin>>n)
????{
????????fill(c,n+1);
????????for(i=0;i<n;i++)
????????????cin>>a[i];
????????c[0]=-1;//????…………………………………………1
????????c[1]=a[0];//????????……………………………………2
????????b[0]=1;//?????…………………………………………3
????????for(i=1;i<n;i++)//????????………………………………4
????????{
????????????j=find(c,n+1,a[i]);//???……………………5找到長(zhǎng)度最大的并且結(jié)尾小于a[i]
????????????c[j]=a[i];//?………………………………6
????????????b[i]=j;//……………………………………7
????????}
????????for(max=i=0;i<n;i++)//………………………………8
????????????if(b[i]>max)
????????????????max=b[i];
????????cout<<max<<endl;
????}
????return?0;
}

對(duì)于這段程序，我們可以用算法導(dǎo)論上的loop invariants來(lái)幫助理解.
????loop invariant: 1、每次循環(huán)結(jié)束后c都是單調(diào)遞增的。(這一性質(zhì)決定了可以用二分查找）
?????????????????????????? 2、每次循環(huán)后，c[i]總是保存長(zhǎng)度為i的遞增子序列的最末的元素，若長(zhǎng)度為i的遞增子序

????????????????????????????????? 列有多個(gè)，剛保存末尾元素最小的那個(gè).（這一性質(zhì)決定是第3條性質(zhì)成立的前提）
?????????????????????????? 3、每次循環(huán)完后，b[i]總是保存以a[i]結(jié)尾的最長(zhǎng)遞增子序列。
????initialization:??? 1、進(jìn)入循環(huán)之前，c[0]=-1,c[1]=a[0],c的其他元素均為1000,c是單調(diào)遞增的;
?????????????????????????? 2、進(jìn)入循環(huán)之前，c[1]=a[0],保存了長(zhǎng)度為1時(shí)的遞增序列的最末的元素，且此時(shí)長(zhǎng)度為1

???????????????????????????????? 的遞增了序列只有一個(gè)，c[1]也是最小的;
?????????????????????????? 3、進(jìn)入循環(huán)之前，b[0]=1，此時(shí)以a[0]結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度為1.
????maintenance:?? 1、若在第n次循環(huán)之前c是單調(diào)遞增的，則第n次循環(huán)時(shí)，c的值只在第6行發(fā)生變化，而由

??????????????????????????????? c進(jìn)入循環(huán)前單調(diào)遞增及find函數(shù)的性質(zhì)可知（見(jiàn)find的注釋),

???????????????????????????????? 此時(shí)c[j+1]>c[j]>=a[i]>c[j-1],所以把c[j]的值更新為a[i]后，c[j+1]>c[j]>c[j-1]的性質(zhì)仍然成

??????????????????????????????? 立，即c仍然是單調(diào)遞增的；
?????????????????????????? 2、循環(huán)中，c的值只在第6行發(fā)生變化，由c[j]>=a[i]可知，c[j]更新為a[i]后，c[j]的值只會(huì)變

????????????????????????????????? 小不會(huì)變大，因?yàn)檫M(jìn)入循環(huán)前c[j]的值是最小的，則循環(huán)中把c[j]更新為更小的a[i]，當(dāng)

???????????????????????????????? 然此時(shí)c[j]的值仍是最小的;
???????????????? ????????? 3、循環(huán)中，b[i]的值在第7行發(fā)生了變化，因?yàn)橛衛(wèi)oop invariant的性質(zhì)2，find函數(shù)返回值

??????????????????????????????? 為j有：c[j-1]<a[i]<=c[j],這說(shuō)明c[j-1]是小于a[i]的，且以c[j-1]結(jié)尾的遞增子序列有最大的

?????????????????????????????? 長(zhǎng)度，即為j-1,把a(bǔ)[i]接在c[j-1]后可得到以a[i]結(jié)尾的最長(zhǎng)遞增子序列，長(zhǎng)度為(j-1)+1=j;
????termination:?????? 循環(huán)完后，i=n-1,b[0],b[1],...,b[n-1]的值均已求出，即以a[0],a[1],...,a[n-1]結(jié)尾的最長(zhǎng)遞

????????????????????????????? 增子序列的長(zhǎng)度均已求出，再通過(guò)第8行的循環(huán)，即求出了整個(gè)數(shù)組的最長(zhǎng)遞增子序列。

????????? 仔細(xì)分析上面的代碼可以發(fā)現(xiàn)，每次循環(huán)結(jié)束后，假設(shè)已經(jīng)求出c[1],c[2],c[3],...,c[len]的值，則此時(shí)最長(zhǎng)遞增子序列的長(zhǎng)度為len,因此可以把上面的代碼更加簡(jiǎn)化，即可以不需要數(shù)組b來(lái)輔助存儲(chǔ)，第8行的循環(huán)也可以省略。

二分查找可以參考：http://blog.csdn.net/sunmenggmail/article/details/7540970

#include?<iostream>
using?namespace?std;
int?find(int?*a,int?len,int?n)//修改后的二分查找，若返回值為x，則a[x]>=n
{
????int?left=0,right=len,mid=(left+right)/2;
????while(left<=right)
????{
????????if(n>a[mid])?left=mid+1;
????????else?if(n<a[mid])?right=mid-1;
????????else?return?mid;
????????mid=(left+right)/2;
????}
????return?left;
}
int?main()
{
????int?n,a[100],c[100],i,j,len;//新開(kāi)一變量len,用來(lái)儲(chǔ)存每次循環(huán)結(jié)束后c中已經(jīng)求出值的元素的最大下標(biāo)
????while(cin>>n)
????{
????????for(i=0;i<n;i++)
????????????cin>>a[i];
????????b[0]=1;
????????c[0]=-1;
????????c[1]=a[0];
????????len=1;//此時(shí)只有c[1]求出來(lái)，最長(zhǎng)遞增子序列的長(zhǎng)度為1.
????????for(i=1;i<n;i++)
????????{
????????????j=find(c,len,a[i]);
????????????c[j]=a[i];
????????????if(j>len)//要更新len,另外補(bǔ)充一點(diǎn)：由二分查找可知j只可能比len大1
????????????????len=j;//更新len
????????}
????????cout<<len<<endl;
????}
????return?0;
}

總結(jié)

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

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