求一个字符串的最长递增子序列的长度 如:dabdbf 最长递增子序列就是 abdf,长度为 4
时间: 2023-07-28 08:19:11 浏览: 43
这是一个经典的动态规划问题。可以使用一个一维数组dp来记录以每个字符结尾的最长递增子序列的长度。初始时,每个字符自成一个长度为1的递增子序列,即dp数组全为1。然后遍历字符串,对于每个字符,再遍历它前面的所有字符,如果比当前字符小,则可以将当前字符接到这个字符的子序列后面形成一个新的递增子序列,更新dp数组。最后dp数组中的最大值就是所求的最长递增子序列的长度。以下是示例代码:
```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)
# 示例
s = 'dabdbf'
print(longest_increasing_subsequence(s)) # 输出 4
```
相关问题
求一个字符串最长递增子序列长度
可以使用动态规划来解决这个问题。
假设给定字符串为 `s`,长度为 `n`。我们可以定义一个数组 `dp`,其中 `dp[i]` 表示以第 `i` 个字符结尾的最长递增子序列的长度。
那么,对于每个字符 `s[i]`,它的最长递增子序列长度至少为 1,即 `dp[i] = 1`。然后我们枚举前面所有比 `s[i]` 小的字符 `s[j]`,如果 `s[j]` 可以接在 `s[j]` 的后面形成一个递增子序列,那么就更新 `dp[i]`,即 `dp[i] = max(dp[i], dp[j] + 1)`。
最终,最长递增子序列的长度就是 `dp` 数组中的最大值。
下面是 Python 代码实现:
```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)
```
时间复杂度为 $O(n^2)$。
题目描述 求一个字符串的最长递增子序列的长度 如:dabdbf 最长递增子序列就是 abdf,长度为 4 输入描述 第一行一个整数 0<n<20, 表示有 n 个字符串要处理 随后的 n 行,每行有一个字符串,该字符串的长度不会超过 10000 输出描述 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7
你可以按照上面的思路,对每个字符串分别求解最长递增子序列的长度。以下是示例代码:
```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
```