本文共 1081 字，大约阅读时间需要 3 分钟。

描述

求一个字符串的最长递增子序列的长度

如：dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0<n<20,表示有n个字符串要处理

随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

输出字符串的最长递增子序列的长度

样例输入

3aaaababcabklmncdefg

样例输出

137

来源

/**********************************   日期：2013-3-25*   作者：SJF0115*   题号: 题目17: 单调递增最长子序列*   来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=17*   结果：AC*   来源：南阳理工OJ*   总结：**********************************/#include
      
       #include
       
        char array[10001];int MaxLen[10001];//最长递增子序列void LIS(){	memset(MaxLen,0,sizeof(MaxLen));	int len = strlen(array);	for(int i = 0;i < len;i++){		MaxLen[i] = 1;		for(int j = 0;j < i;j++){			if(array[i] > array[j]){				if(MaxLen[i] < 1 + MaxLen[j]){					MaxLen[i] = 1 + MaxLen[j];				}			}		}	}}int main(){	int N,i,len,Max;	//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);	scanf("%d",&N);	//N组测试数据	while(N--){		Max = 0;		scanf("%s",array);		LIS();		len = strlen(array);		//输出最大长度		for(i = 0;i < len;i++){			if(Max < MaxLen[i]){				Max = MaxLen[i];			}		}		printf("%d\n",Max);	}	return 0;}
       
      

具体参考：

转载地址：http://aucsi.baihongyu.com/