動(dòng)歸之最長上升子序列

信息科學(xué)技術(shù)學(xué)程序設(shè)計(jì)實(shí)劉家1信息科學(xué)技術(shù)學(xué)院《程序設(shè)計(jì)實(shí)習(xí)》劉家最長上升子序2一個(gè)數(shù)的序列ai，當(dāng)a1<a2<...<aS的時(shí)候，我們稱這個(gè)序列是上升的。對(duì)于給定的一個(gè)序列(a1,a2,...,aN)，我們可以得到一些上升的子序列(ai1,ai2,...,aiK)，這里1<=i1<i2iKN。比如，對(duì)于序列(1,7,35,9,4,8)，有它的一些上升子序列，如(17)(348)列中最長的長度是4，比如子序列(1,353輸入的第一行是序列的長度N1N1000)。第二行給出717359444找子假設(shè)F(n)=x,但可能有多個(gè)序列滿足F(n)=x。有的序列的最后一個(gè)元素比an+1小，則加上an+1就能形成更長上5“求以ak（k=1,2,3…N）為終點(diǎn)的最長上升子序列的6確定狀態(tài)子問題只和一個(gè)變量--數(shù)字的位置相關(guān)。因此序列中數(shù)的位置k是“狀態(tài)”，而狀k應(yīng)的“值”，就是以ak狀態(tài)一共有N7maxLen(k)表示以ak做為“終點(diǎn)”的初始狀態(tài)：maxLen(1)maxLen(k)maxmaxLeni)：1<=ik若找不到這樣的i,則maxLen(k)=

akk≠1maxLen(k)的值，就是在ak左邊，“終點(diǎn)”數(shù)值小于ak，且長度8#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;

constintMAXNintintmain()

intint cin>>for(inti=1;i<=N;++i)cin>>maxLen[i]=}for(inti2iN;i)//每次求以第i個(gè)數(shù)為終點(diǎn)的最長上升子序列的長度for(intj=1;j<i;++j)//察看以第j個(gè)數(shù)為終點(diǎn)的最長上升子序列if(a[i]>a[j]maxLen[i]=}cout<<*max_element(maxLen+1,maxLen+N+1return}//時(shí)間復(fù)雜度 i i #include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;

constintMAXN=1010;inta[MAXN];intfor(intifor(inti=2;i<=N;for(intj=1;j<i;++j)if(a[i]>a[j])maxLen[i]int cin>>for(inti=1;i<=N;++i)cin>>maxLen[i]=}for(inti=1;i<=N;for(intj=i+1;j<=N;++j) if(a[j]>a[i])maxLen[j]=c