Russian doll envelops
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