805
技術社區[雲棲]
WIKIOI-1576 最長不下降子序列
題目描述 Description
給一個數組a1, a2 ... an，找到最長的不下降子序列ab1<=ab2<= .. <=abk，其中b1<b2<..bk。
輸出長度即可。
輸入描述 Input Description
第一行，一個整數N。
第二行 ，N個整數（N < = 5000）
輸出描述 Output Description
輸出K的極大值，即最長不下降子序列的長度
樣例輸入 Sample Input
5
9 3 6 2 7
樣例輸出 Sample Output
3
數據範圍及提示 Data Size & Hint
【樣例解釋】
最長不下降子序列為3,6,7
本題是經典的動態規劃練習題（代碼有錯誤，已修改，感謝hpuhjl指出錯誤！）
//一般方法（非動態規劃的方法）。動態規劃方法暫時沒寫，會在以後寫出來
#include<stdio.h>
#include<string.h>
#include<limits.h>
int num[5010],lin[5010];
int Fun(int n)
{
int i,j,max;
for(i=0;i<n;i++)
lin[i]=1;
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
if(num[i]>num[j]&&lin[i]<lin[j]+1)
lin[i]=lin[j]+1;
}
max=-1;
for(i=0;i<n;i++)
if(lin[i]>max)
max=lin[i];
return max;
}
int main()
{
int i,j,n,m;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&num[i]);
}
printf("%d\n",Fun(n));
return 0;
}
最後更新：2017-04-03 12:55:35