输入一行字符串,该字符串只由小写英文字母a-z组成,且其中的字符可以重复,最长不超过10000个字符。 从该字符串中按顺序挑选出若干字符(不一定相邻)组成一个新串,称为"子串"。如果子串中每两个相邻的字符或者相等,或者后一个比前一个大,则称为"升序子串"。编程求出输入字符串的最长升序子串的长度。 例如,由输入字符串abdbch可以构成的升序子串有:abd、abch、bbch、abbch等。其中最长的升序子串是abbch,其长度为5。 【输入形式】 从标准输入读取一行字符串,该串不含空格,以回车符结束。 【输出形式】 向标准输出打印一个正整数,是字符串中最长的升序子串的长度,在行末要输出一个回车符。
时间: 2024-03-23 16:40:38 浏览: 218
这道题可以使用动态规划的方法来解决。我们可以定义一个数组dp,其中dp[i]表示以第i个字符结尾的最长升序子串的长度。对于第i个字符,它可以单独成为一个长度为1的升序子串,也可以和前面的字符组成一个新的升序子串。如果第i个字符比前面的字符大,那么可以将第i个字符加入到前面的升序子串中;否则,第i个字符只能单独成为一个长度为1的升序子串。
以下是Python代码:
```python
s = input()
n = len(s)
# 初始化dp数组
dp = [1] * n
# 动态规划
for i in range(1, n):
if s[i] > s[i-1]:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
# 输出结果
print(max(dp))
```
输入样例:
```
abdbch
```
输出样例:
```
5
```
阅读全文