Maximum number of envelopes that can be put inside other bigger envelopes | Function that returns the maximum number of envelopes that can be inserted into another envelopes ; Number of envelopes ; Sort the envelopes in non - decreasing order ; Initialize dp [ ] array ; To store the result ; Loop through the array ; Find envelopes count for each envelope ; Store maximum envelopes count ; Return the result ; Given the envelopes ; Function Call
function maxEnvelopes ( envelopes ) { var N = envelopes . length ; if ( N == 0 ) return N ; envelopes . sort ( ) ; var dp = Array ( N ) ; var max_envelope = 1 ; dp [ 0 ] = 1 ; for ( var i = 1 ; i < N ; ++ i ) { dp [ i ] = 1 ; for ( var j = 0 ; j < i ; ++ j ) { if ( envelopes [ i ] [ 0 ] > envelopes [ j ] [ 0 ] && envelopes [ i ] [ 1 ] > envelopes [ j ] [ 1 ] && dp [ i ] < dp [ j ] + 1 ) dp [ i ] = dp [ j ] + 1 ; } max_envelope = Math . max ( max_envelope , dp [ i ] ) ; } return max_envelope ; } var envelopes = [ [ 4 , 3 ] , [ 5 , 3 ] , [ 5 , 6 ] , [ 1 , 2 ] ] ; document . write ( maxEnvelopes ( envelopes ) ) ;