描述
求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4
输入第一行一个整数0<n<20,表示有n个字符串要处理 随后的n行,每行有一个字符串,该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入
3
aaa
ababc
abklmncdefg
样例输出
1
3
7
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
#include <memory.h>
#include <string>
#include <math.h>
using namespace std;
char ch[10005];
int dis[10005];
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>ch;
dis[0] = 1;
int max_ = 1;
for(int i=0;i<strlen(ch);i++)
{
dis[i] = 1;
for(int j=0;j<i;j++)
{
if(ch[j] < ch[i])
dis[i] = max(dis[i],dis[j]+1);
if(dis[i] >= max_)
max_ = dis[i];
}
}
cout<<max_<<endl;
}
return 0;
}