問題描述
一個數(shù)的序列bi，當(dāng)b1 < b2 < … < bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1, a2, …, aN)，我們可以得到一些上升的子序列(ai1, ai2, …, aiK)，這里1 <= i1 < i2 < … < iK <= N。比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長的長度是4，比如子序列(1, 3, 5, 8). 你的任務(wù)，就是對于給定的序列，求出最長上升子序列的長度
代碼片
#include <stdio.h> #define MAX 1000 int seq[MAX+10]; int seqlen[MAX+10]; int main() { int i,j,k,N,max,maxlen=1; //maxlen賦值為1 for(i=1;i<=9;i++) seqlen[i]=1; //seqlen數(shù)組存以第i個數(shù)為終點(diǎn)的最長上升序列 scanf("%d",&N); //輸入長度N for(i=1;i<=N;i++) scanf("%d",&seq[i]); //seq數(shù)組保存序列數(shù)組 for (i=2;i<=N;i++) { max=0; //將max最小化 for (j=1;j<=i-1;j++) { if(seq[j]<seq[i]&&seqlen[j]>max) //在前i-1個序列中，尋找以終點(diǎn)小于seq[i]的最長的子序列，即最優(yōu)子狀態(tài) max=seqlen[j]; } seqlen[i]=max+1; if(seqlen[i]>maxlen) //seqlen中保存的是第i個數(shù)為終點(diǎn)的最長上升序列，找出這個數(shù)組中最大的值即為最優(yōu)序列長度 maxlen=seqlen[i]; }
