Longest increasing subsequence in O(n) time?
<p>I'm studying this algorithm for the first time.  CLRS (15-4.6) asks to write an algorithm to run in O(n lg n) time.  The algorithm I came up with seems to run in O(n).  I think I must be misunderstanding something, because even wikipedia says it should take O(n lg n) time.  (<a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence" rel="nofollow">https://en.wikipedia.org/wiki/Longest_increasing_subsequence</a>)<br>
Could somebody tell me why this algorithm (in Python) doesn't work in general or isn't O(n) or doesn't answer the question??</p>

<pre><code>"""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] &gt; first[-1]:
            second = first[:]
            first.append(n[i])
        elif not second or n[i] &gt; 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])
</code></pre>

<p>I'll leave some of the debugging to you, but the following does not produce the maximum length substring using your algorithm. I simply added a few numbers to the example you had, so it should have produced <code>[0, 4, 6, 9, 11, 15]</code> again, but didn't:</p>

<pre><code>&gt;&gt;&gt; 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]
</code></pre>

python algorithm longest-substring