【C语言】之''最长升序子串''

老师平时布置的希冀系统上的作业答案,仅供参考!

【问题描述】

输入一行字符串,该字符串只由小写英文字母a-z组成,且其中的字符可以重复,最长不超过10000个字符。
从该字符串中按顺序挑选出若干字符(不一定相邻)组成一个新串,称为“子串”。如果子串中每两个相邻的字符或者相等,或者后一个比前一个大,则称为“升序子串”。编程求出输入字符串的最长升序子串的长度。
例如,由输入字符串abdbch可以构成的升序子串有:abd、abch、bbch、abbch等。其中最长的升序子串是abbch,其长度为5。

【输入形式】

从标准输入读取一行字符串,该串不含空格,以回车符结束。

【输出形式】

向标准输出打印一个正整数,是字符串中最长的升序子串的长度,在行末要输出一个回车符。

【输入样例】

abdbch

【输出样例】

5

【样例说明】

abdbch中最长子串是abbch,长度是5。

【参考答案】

#include <stdio.h>
#include <string.h>
#define MAXN 10000
#define MAX(x,y) ((x)>(y) ? (x) : (y))

int main()
{
char s[MAXN+1];
int i,j;
int dp[MAXN];
int max;
gets(s);
dp[0] = 1;
for(i=1;s[i]!='\0';i++)
{
dp[i] = 1;
for(j=0;j<i;j++)
{
if(s[i]>=s[j])
if(dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
max = dp[0];
for(i=1;s[i]!='\0';i++)
{
max = MAX(max,dp[i]);
}

printf("%d\n",max);

return 0;
}
© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容