O(n) 时间内最长的递增子序列？

Question

第一次学习这个算法。 CLRS (15-4.6) 要求在 O(n lg n) 时间内将算法写入运行。我想出的算法似乎在 O(n) 中运行。我想我一定是误解了什么，因为即使是维基百科也说它应该花费 O(n lg n) 时间。 (https://en.wikipedia.org/wiki/Longest_increasing_subsequence)
有人能告诉我为什么这个算法（在 Python 中）一般不起作用或者不是 O(n) 或不回答问题吗？？

"""Attempts to find maximal ordered subsequence in linear time."""

def subseq(n):
    """Assumes the elements of n are unique"""
    if len(n) == 1:
        return n[:]
    first = [n[0]]
    second = []
    for i in range(1,len(n)):
        if n[i] > first[-1]:
            second = first[:]
            first.append(n[i])
        elif not second or n[i] > second[-1]:
            first = second[:]
            first.append(n[i])
    return first

print subseq([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])

Answer 1

我会将一些调试工作留给您，但以下内容不会使用您的算法生成最大长度子字符串。我只是在你的例子中添加了一些数字，所以它应该再次产生 [0, 4, 6, 9, 11, 15]，但没有：

>>> print(subseq([0, 12,12,15,14 ,8, 4, 12, 14, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))
[0, 12, 13, 15]

O(n) 时间内最长的递增子序列？

Longest increasing subsequence in O(n) time?

python

algorithm

longest-substring