C语言输入一个小写英文字符串,求其中按字母顺序严格递增最长的序列及其长度,例如:输入abcbefizkl,则最长序列为 befiz,长度为 5;输入dabbhpke, 则最长序列未bhpk,长度未4。 输入 一个由小写英文字母构成的字符串,长度不超过100 输出 最长严格递增序列及其长度,中间用空格隔开
时间: 2023-10-09 18:12:54 浏览: 168
以下是C语言的实现代码:
```c
#include <stdio.h>
#include <string.h>
int main()
{
char str[101];
int dp[101], pre[101], len, pos, max_len = 0, max_pos = 0;
scanf("%s", str);
len = strlen(str);
for (int i = 0; i < len; i++)
{
dp[i] = 1;
pre[i] = -1;
for (int j = 0; j < i; j++)
{
if (str[j] < str[i] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] > max_len)
{
max_len = dp[i];
max_pos = i;
}
}
char ans[101];
pos = max_pos;
for (int i = max_len - 1; i >= 0; i--)
{
ans[i] = str[pos];
pos = pre[pos];
}
printf("%s %d\n", ans, max_len);
return 0;
}
```
思路解析:
本题可以使用动态规划来解决。我们定义 dp[i] 表示以第 i 个字符结尾的最长严格递增子序列的长度,pre[i] 表示以第 i 个字符结尾的最长严格递增子序列中,i 的前一个字符的位置。那么,我们可以得到状态转移方程:
$$
dp[i]=\max_{j=0}^{i-1}\{dp[j]+1\}, \text{s.t. } str[j]<str[i]
$$
表示在所有满足 str[j] < str[i] 的 j 中,选择 dp[j] 最大的一个再加上 i,就是以 i 结尾的最长严格递增子序列的长度。同时,我们记录一下 dp 数组中最大值的位置 max_pos,那么以该位置为结尾的最长严格递增子序列就是我们所求。
最后,我们通过 pre 数组从 max_pos 开始,倒序遍历 dp 数组,就可以得到最长严格递增子序列。