Russian doll envelops Interview question from the interwebz


  You have a set of envelopes of different widths and heights.  One
  envelope can fit into another if and only if both the width and height
  of one envelope is greater than the width and height of the other
  envelope. What is the maximum number of envelopes can you russian
  doll?


My implementation:

# assuming no dups
def max_russian_doll(enve):
    if not enve: return 0
    enve.sort()
    max_global = 1
    for j in xrange(len(enve) - 1):
        max_local = 1
        for i in xrange(j, len(enve) - 1):
            if enve[i][1] &lt; enve[i + 1][1] and enve[i][0] != enve[i + 1][0]: # @comment 
                max_local += 1
        max_global = max(max_global, max_local)    
    return max_global

envelopes = [(4,5), (6,7), (2,3)]  
max_russian_doll(envelopes)


obviously this is \$O(n^2)\$. Right now I'm trying to figure out faster solution. Any tips?
Using LIS from Wikipedia.

def max_russian_doll(seq):
    if not seq: return 0
    seq.sort()
    M = [0] * (len(seq) + 1)
    L = 1
    for i in xrange(len(seq)):
        lo = 1
        hi = L
        while lo &lt;= hi:
            mid = (hi - lo)/2 + lo
            if seq[M[mid]][1] &lt; seq[i][1] and seq[M[mid]][0] &lt; seq[i][0]:
                lo = mid + 1
            else:
                hi = mid - 1
        newL = lo
        if newL &gt; L:
            M[newL] = i
            L = newL
    return L

print max_russian_doll([]) == 0
print max_russian_doll([(1,1)]) == 1 
print max_russian_doll([(1,1), (1,1), (1,1)]) == 1
print max_russian_doll([(4,5), (4,6), (6,7), (2,3), (1,1)]) == 4 # e.g (1,1) -&gt; (2,3) -&gt; (4,5) -&gt; (6,7)
print max_russian_doll([(4,5), (4,6), (6,7), (2,3), (1,1), (1,1)]) == 4
print max_russian_doll([(5,4), (6,4), (6,7), (2,3)]) == 3