单调递增最长子序列
时间限制:3000 ms | 内存限制:65535 KB
难度:4
描述
求一个字符串的最长递增子序列的长度
如:dabdbf最长递增子序列就是abdf,长度为4输入
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行,每行有一个字符串,该字符串的长度不会超过10000
输出
输出字符串的最长递增子序列的长度
样例输入
3
aaa
ababc
abklmncdefg
样例输出
1
3
7
1 #include<stdio.h>
2 #include<string.h>
3 int main(){char s[10010],dp[10010],maxlen;
4 int n;
5 scanf("%d",&n);
6 while(n--){
7 memset(dp,0,sizeof(dp));
8 scanf("%s",s);
9 dp[0]=1;
10 maxlen=1;
11 for(int i=1;s[i];i++){dp[i]=1;
12 for(int j=0;j<i;j++){
13 if(s[j]<s[i]){
14 dp[i]=dp[j]+1>dp[i]?dp[j]+1:dp[i];
15 }
16 }
17 maxlen=dp[i]>maxlen?dp[i]:maxlen;
18 }
19 printf("%d\n",maxlen);
20 }
21 return 0;
22 }//camnbdef