653
NYOJ17-單調遞增最長子序列
單調遞增最長子序列
時間限製：3000 ms | 內存限製：65535 KB
難度：4
描述
求一個字符串的最長遞增子序列的長度
如：dabdbf最長遞增子序列就是abdf，長度為4
輸入
第一行一個整數0<n<20,表示有n個字符串要處理
隨後的n行，每行有一個字符串，該字符串的長度不會超過10000
輸出
輸出字符串的最長遞增子序列的長度
樣例輸入
3
aaa
ababc
abklmncdefg
樣例輸出
1
3
7
來源
經典題目
AC代碼：
#include<stdio.h>
#include<string.h>
char a[10010];
int num[10010];
int Fun(char a[],int m)
{
int i,j,max=0;
for(i=0;i<m;i++)
num[i]=1;
for(i=1;i<m;i++)
for(j=0;j<i;j++)
if(a[i]>a[j]&&num[i]<num[j]+1)
num[i]=num[j]+1;
for(i=0;i<m;i++)
if(num[i]>max)
max=num[i];
return max;
}
int main()
{
int i,j,n,m,t,flag;
scanf("%d",&n);
while(n--)
{
memset(a,0,sizeof(a));
getchar();
scanf("%s",a);
m=strlen(a);
printf("%d\n",Fun(a,m));
}
return 0;
}
最後更新：2017-04-03 12:56:01