Sort the envelopes by either area or sum of dimensions, as long as the ith envelope can only contain those with index
For each envelope
mx[i], the maximum number of envelopes that can
i can "russian-doll", including itself. For the smallest envelope,
i>0, take the russian-doll max of any envelope
ii: ii<i to its left as long
i can "russian-doll"
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