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

Question

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

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,7,6,3,9,5,4,1}。

现在我想求S中最长递增子序列的长度，在上面的示例中:5->{1,2,4,7,9}

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

Answer 1

最长递增子序列的长度不能大于2。因为你连接的序列是递减的，所以如果你从一个序列的最后一个数到另一个序列的第一个数，它只能是递增的序列。要找出序列S中是否存在长度为2的递增子序列，您只需关注要连接的序列的结尾和开头。