问一组不相交递减序列的最长增长子序列
EN

Stack Overflow用户

提问于 2014-10-05 07:11:20

回答 1查看 293关注 0票数 0

假设我们有一些不相交的递减序列：

s1={10,8,2}
s2={9,5,4,1}
s3={7,6,3}

我选择了一些递减序列(例如按s2、s1、s2、s3、s2顺序排列的5个递减序列)并将它们连接起来(结果是序列S = {9,5,4,1,10,8,2,9,5,4,1,7,6,3,9,5,4,1} )。

现在我想找出S中最长增长子序列的长度。在上面的示例中：5 -> {1,2,4,7,9}

预期的时间复杂度小于O( less )。

发布于 2014-10-05 07:54:18

最长的增长子序列的长度不能超过两个。因为连接的序列在减少，所以只有当从一个序列的最后一个数转到另一个序列的第一个数时，它才能是一个递增序列。要找出序列S中是否存在长度为2的递增子序列，只需将焦点放在要连接的序列的末尾和开头。

票数 -1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/26200468

复制

相似问题

问一组不相交递减序列的最长增长子序列EN