单调递增最长子序列

单调递增最长子序列

 

时间限制：3000 ms  |  内存限制：65535 KB

 

难度：4

 

描述

求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

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

样例输入

3
aaa
ababc
abklmncdefg

样例输出

1
3
7

   思路：

   题意简明易懂，所以不作解释。最基本的动态规划题，设 i 为当前位置，max[ i ]为当前位置的单调递增的最大长度，则max[ i ] = max{max[ i-1 ],max[ i-2 ],max[ i-3 ]......max[ 0 ]}+1（判断条件为s[ i ]>s[ ? ]）,故算当前最大长度时，应设另外一个变量j从0开始到i进行遍历，找到最大的一项max [ j ]进行+1再赋值于max[ i ]。故 i 应从1遍历到length。数组中最大max[ i ]值即为最长递增子序列的长度。（一开始全部max数组的值都初始化为1）

  AC：

#include<stdio.h>
#include<string.h>
int main()
{
   int n,length,i,j,m;
   char s[10005];
   int max[10005];
   scanf("%d",&n);
   while(n--)
   {
   	scanf("%s",s);
   	length=strlen(s);
   	for(i=0;i<length;i++)
   	  max[i]=1;
//初始化为1不为0，因为最长子序列长度最坏的情况就是1
//即不存在这样的单调递增序列，每个数都是一个单独的递增长度，长度为1
   	  m=1;
//同理，最大值也应该是1，记得m的初始化在循环内进行，非循环外
//从前递推到后，i在前j在后，故判断条件应该是s[j]>s[i]
   	for(i=1;i<length;i++)
   	{
   		for(j=0;j<i;j++)
   		 if(s[i]>s[j])
   		  max[i]=max[i]>max[j]+1?max[i]:max[j]+1;
//每个max[i]都为当前位置i为止的最大长度情况，但这不代表max数组最后一个值肯定为最大
   		if(max[i]>m) m=max[i];  
//在最大值，无需另外开个循环再判断
   	}
   	printf("%d\n",m);
   }
   return 0;	
}

   总结：

   在学新知识的时候应该找相对简单的题来练练手，以至于不生疏，于是大晚上的拿了道动态规划最基本的题来做。需要注意的地方还是有的，越简单出错的几率就越大，考虑循环边界的问题，还有最大值的初始化问题，这是之前一直出错的地方。