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]))
[0, 12, 13, 15]