最长递增子序列的长度

系统 1608 0
【描述】
求一个字符串的最长递增子序列的长度
如: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。 

 

最长递增子序列的长度


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论