Python implementation of the longest increasing subsequence
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 &lt;= L such that: X[M[j]] &lt; 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]] &lt; 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]] &lt; X[i]):
                    start += partition
                    j = start
                else:
                    end = start + partition - 1

        if (j &gt;= 0):
            P.append(M[j])
        else:
            P.append(-1)

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

    ## trace subsequence back to output
    result = []
    trace_idx = M[L-1]
    while (trace_idx &gt;= 0):
        result.append(X[trace_idx])
        trace_idx = P[trace_idx]

    return list(result.__reversed__())


use reversed(list)

l1 = randomList(15,100)