Prompted by this question on Stackoverflow, I wrote an implementation in Python of the longest increasing subsequence problem. In a nutshell, the problem is: given a sequence of numbers, remove the fewest possible to obtain an increasing subsequence (the answer is not unique). Perhaps it is best illustrated by example.
>>> elems [25, 72, 31, 32, 8, 20, 38, 43, 85, 39, 33, 40, 98, 37, 14] >>> subsequence(elems) [25, 31, 32, 38, 39, 40, 98]
The code below works, but I am sure it could be made shorter and / or more readable. Can any more experienced Python coders offer some suggestions?
edited to add a description: The algorithm iterates over the input array,
X, while keeping track of the length longest increasing subsequence found so far (
L). It also maintains an array
M of length
M[j] = "the index in
X of the final element of the best subsequence of length
j found so far" where best means the one that ends on the lowest element. It also maintains an array
P which constitutes a linked list of indices in
X of the best possible subsequences (e.g.
P[j], P[P[j]], P[P[P[j]]] ... is the best subsequence ending with
X[j], in reverse order).
P is not needed if only the length of the longest increasing subsequence is needed.
from random import randrange from bisect import bisect_left def randomList(N, max): return [randrange(max) for x in xrange(N)] def subsequence(seq): """Returns the longest subsequence (non-contiguous) of seq that is strictly increasing. """ # head[j] = index in 'seq' of the final member of the best subsequence # of length 'j + 1' yet found head =  # predecessor[j] = linked list of indices of best subsequence ending # at seq[j], in reverse order predecessor = [-1] for i in xrange(1, len(seq)): ## Find j such that: seq[head[j - 1]] < seq[i] <= seq[head[j]] ## seq[head[j]] is increasing, so use binary search. j = bisect_left([seq[head[idx]] for idx in xrange(len(head))], seq[i]) if j == len(head): head.append(i) if seq[i] < seq[head[j]]: head[j] = i predecessor.append(head[j - 1] if j > 0 else -1) ## trace subsequence back to output result =  trace_idx = head[-1] while (trace_idx >= 0): result.append(seq[trace_idx]) trace_idx = predecessor[trace_idx] return result[::-1] l1 = randomList(15, 100)