Python implementation of the longest increasing subsequence

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

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 = [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,X.__len__()):
## Find largest j = 0):
P.append(M[j])
else:
P.append(-1)

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

from random import randrange
from itertools import islice

def randomSeq(max):

The python style guide recommend that you use space_with_underscores for function names

while True: yield randrange(max)

def randomList(N,max):
  return list(islice(randomSeq(max),N))

I suspect that's not a really efficient way to produce a random list. I think the following may be a better option:

return [randrange(max) for x in range(N)]

I've not done any benchmarking so I may be wrong.

## 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]

Consider using names instead of these single letter variables.

for i in range(1,X.__len__()):

Don't use x.__len__() use len(x)

## Find largest j <= L such that: X[M[j]] < X[i].
        ## X[M[j]] is increasing, so use binary search over j.

This whole bit about the binary search would do well in a seperate function so as not the clutter the subsequence implementation. Actually python already provides a binary search function in the bisect module.

j = -1
        start = 0
        end = L - 1
        going = True
        while going:
            if (start == end):

You don't need those parens

if (X[M[start]] < X[i]):
                    j = start
                going = False

Use break. break isn't pretty when you can avoid it, but setting booleans flags is worse.

else:
                partition = 1 + ((end - start - 1) / 2)

Notice how you only use start + partition? Calculate the middle element instead. It'll make this whole section a bit neater.

if (X[M[start + partition]] = 0):
            P.append(M[j])
        else:
            P.append(-1)

        j += 1
        if (j == L):
            M.append(i)
            L += 1
        if (X[i] = 0):
        result.append(X[trace_idx])
        trace_idx = P[trace_idx]

    return list(result.__reversed__())

use reversed(list)

l1 = randomList(15,100)

StackExchange Code Review Q#10230, answer score: 5