题目描述 求一个字符串的最长递增子序列的长度 如:dabdbf 最长递增子序列就是 abdf,长度为 4 输入描述 第一行一个整数 0<n<20, 表示有 n 个字符串要处理 随后的 n 行,每行有一个字符串,该字符串的长度不会超过 10000 输出描述 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7
时间: 2024-01-17 08:03:00 浏览: 69
第三章 python基础(csdn)————程序.pdf
你可以按照上面的思路,对每个字符串分别求解最长递增子序列的长度。以下是示例代码:
```python
def longest_increasing_subsequence(s):
n = len(s)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if s[j] < s[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 主函数
n = int(input())
for i in range(n):
s = input().strip()
print(longest_increasing_subsequence(s))
```
输入示例:
```
3
aaa
ababc
abklmncdefg
```
输出示例:
```
1
3
7
```
阅读全文