首页 > 代码库 > 单调递增连续最长子序列

单调递增连续最长子序列

描述
求一个字符串的最长递增子序列[字母保持原顺序连续]的长度
如:dabdbf最长递增子序列就是abd,长度为3
输入
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行,每行有一个字符串,该字符串的长度不会超过10000
输出
输出字符串的最长递增字典序的长度[序列字符保持连续]
样例输入
3
aaa
ababc
abklmncdefg
样例输出
1
3
6
#include<stdio.h>
#include<string.h>
int main()
{
	int n;
	char str[10010];
	scanf("%d",&n);getchar();
	while(n--)
	{
		int i=0,j,max=0;
		gets(str);
		int len=strlen(str);
		for(;i<len;++i)
		{
			for(j=i;j<len-1;++j)
			{
				if(str[j]>=str[j+1])
				{
					max=max<j-i+1?j-i+1:max;
					i=j;
					break;
				}
			}
			if(j==len-1)
			{
				max=max<len-i?len-i:max;
				//printf("max=%d##i=%d##len=%d\n",max,i,len);
				break;
			}
		}
		printf("%d\n",max);
	}
	return 0;
}
改编自nyoj-17-单调自增最长子序列

单调递增连续最长子序列