Sort the envelopes by either area or sum of dimensions, as long as the i_{th} envelope can only contain those with index `ii<i`

.

For each envelope `i`

, compute `mx[i]`

, the maximum number of envelopes that can `i`

can "russian-doll", including itself. For the smallest envelope, `mx[0]=1`

. For `i>0`

, take the russian-doll max of any envelope `ii: ii<i`

to its left as long `i`

can "russian-doll" `ii`

.

To help with pruning, record also the maximum seen so far: `gmx[ii]`

after using the first `ii`

envelopes. If at any time, we are at candidate `ii`

and we can already russian-doll at least `gmx[ii]`

envelopes, we know we can stop, since any candidate further on the left will not yield a larger value.

```
class Solution(object):
def maxEnvelopes(self, envs):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
areas=[(w*h, (w,h)) for (w,h) in envs]
areas.sort()
mx=[]
gmxs=[]
gmx=0
for (i,(a,env)) in enumerate(areas):
w,h=env
cnt=0
for ii in xrange(i-1,-1,-1):
aa, env2=areas[ii]
(w2,h2)=env2
if w>w2 and h>h2 and mx[ii]>cnt:
cnt=mx[ii]
if gmxs[ii]<=cnt:
break
cnt+=1
mx.append(cnt)
gmx=max(cnt,gmx)
gmxs.append(gmx)
return gmx
```