O（n）時間で最も長いサブシーケンスが増加しますか？

Question

私はこのアルゴリズムをはじめて研究しています。 CLRS（15-4.6）はO（ng n）時間で実行するアルゴリズムを書くように頼んでいます。私が思いついたアルゴリズムはO（n）で実行されているようです。私は何かを誤解しなければならないと思う.WikipediaでもO（ngng）時間かかるはずだからだ。 （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]