TJ Gaffney - 1 year ago 71
Python Question

# Longest increasing subsequence in O(n) time?

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. (https://en.wikipedia.org/wiki/Longest_increasing_subsequence)

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??

``````"""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])
``````

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 `[0, 4, 6, 9, 11, 15]` again, but didn't:
``````>>> print(subseq([0, 12,12,15,14 ,8, 4, 12, 14, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))