单调递增最长子序列


难度：4

描述 求一个字符串的最长递增子序列的长度
 如：dabdbf最长递增子序列就是abdf，长度为4
输入第一行一个整数0<n<20,表示有n个字符串要处理
 随后的n行，每行有一个字符串，该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度

样例输入
3
aaa
ababc
abklmncdefg

样例输出
1
3
7

盯了一天，愣是没整出来。。

又是南洋理工的题，想看代码还是想听算法？
这题的做法不止一种，不过看起来目前我的代码是关于这题你们学校最短的、占用内存最少的、速度最快的

斑竹给算法吧

版主威武，期待分析加代码。。。
不过题目我好像没理解，感觉题目的例子不对。。。

描述 求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4 // 这个怎么会是4？应该是3 对应的最常字串 是abd （难道可以不连续？）


[ 本帖最后由 BianChengNan 于 2012-2-3 10:20 编辑 ]

哇。。我越来越崇拜你了。。

没有说要连续啊，b和d还不连续呢，只要单调递增就行

我怎么觉得abklmncdefg

的单调递增长度是6？
abklmn不是6个吗 难道后面的c也算个？

先回复楼上，abcdefg的长度是7。

再说这个题的解法。只是我的思路，别人可能有不同的解法，欢迎交流。
设串的字符集为S，包含N个元素，每个元素为Ak，Ai < Aj (0 <= i < j < N)。
设串T中以Ap结尾的单调递增子序列长度为len(T, Ap)，则T的单调递增子序列长度为Maxlen(T) = max(len(T,A0), len(T, A1), ..., len(T,An-1))。
如果给串T的末尾再添加一个字符Aq，则len(T + Aq, Aq) = len(T, Aq - 1) + 1。
由上面的关系可以构造出求串T的单调递增最长子序列的DP算法。在给定的字符集下，该算法的时间复杂度为O(N)。

说起来很抽象，上代码。

#include<stdio.h>
int length(char * s)
{
    int len[128] = {0}, i, t;
    for(; *s != '\0' && (t = len[*s - 1] + 1); s++)
    for(i = *s; i < 128 && len[i] < t; len[i++] = t);
    return len[127];
}
int main()
{
    int n;
    char s[10001];
    for(scanf("%d\n", &n); n--;)
    printf("%d\n", length(gets(s)));
    return 0;
}

我理解成连续单调递增长度了。