单调递增最长子序列
时间限制: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; }