- 【描述】
-
求一个字符串的最长递增子序列的长度
如:dabdbf最长递增子序列就是abdf,长度为4
- 【输入】
-
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行,每行有一个字符串,该字符串的长度不会超过10000 - 【输出】
- 输出字符串的最长递增子序列的长度
方法一:
=================================
=========
用一个数组保存以当前字符作为结束的最长字串
对于一个字符串 s ,申请同样长度的数组 X,X[i] 表示以s[i]结束的最长单调递增子串
X[i] = max{ X[j]+1 } ,其中0≤j<i,且s[j]<s[i]
则s的最长升序子串为 max{ X[i] }
复杂度O(N^2)
方法二:
==========================================
用一数组保存最长长度为下标的最小字符。
方法三:
=======================================================
如果字符的范围有限,那么可以有O(N)时间的算法。
设串的字符集为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。