Prompted by this question on Stack Overflow, 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 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.
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?
from random import randrange from itertools import islice def randomSeq(max): while True: yield randrange(max) def randomList(N,max): return list(islice(randomSeq(max),N)) ## Returns the longest subsequence (non-contiguous) of X that is strictly increasing. def subsequence(X): L = 1 ## length of longest subsequence (initially: just first element) M =  ## M[j] = index in X of the final member of the lowest subsequence of length 'j' yet found P = [-1] for i in range(1,X.__len__()): ## Find largest j <= L such that: X[M[j]] < X[i]. ## X[M[j]] is increasing, so use binary search over j. j = -1 start = 0 end = L - 1 going = True while going: if (start == end): if (X[M[start]] < X[i]): j = start going = False else: partition = 1 + ((end - start - 1) / 2) if (X[M[start + partition]] < X[i]): start += partition j = start else: end = start + partition - 1 if (j >= 0): P.append(M[j]) else: P.append(-1) j += 1 if (j == L): M.append(i) L += 1 if (X[i] < X[M[j]]): M[j] = i ## trace subsequence back to output result =  trace_idx = M[L-1] while (trace_idx >= 0): result.append(X[trace_idx]) trace_idx = P[trace_idx] return list(result.__reversed__()) l1 = randomList(15,100)
See the revised version below, in this answer.