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 L where 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 range(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 = [0]   ## 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,len(X)):
        ## Find j such that:  X[M[j - 1]] < X[i] <= X[M[j]]
        ## X[M[j]] is increasing, so use binary search.
        j = bisect_left([X[M[idx]] for idx in range(L)], X[i])

        if (j == L):
            M.append(i)
            L += 1
        if (X[i] < X[M[j]]):
            M[j] = i

        P.append(M[j - 1] if j > 0 else -1)

    ## 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(reversed(result))