# sub-optimal but simple N^2 python solution, with pruning, accepted

• Sort the envelopes by either area or sum of dimensions, as long as the ith 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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.