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 ; Driver Code ; Given the envelopes ; Function Call
def maxEnvelopes ( envelopes ) : NEW_LINE INDENT N = len ( envelopes ) NEW_LINE if ( N == 0 ) : NEW_LINE INDENT return N NEW_LINE DEDENT envelopes = sorted ( envelopes ) NEW_LINE dp = [ 0 ] * N NEW_LINE max_envelope = 1 NEW_LINE dp [ 0 ] = 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] = 1 NEW_LINE for j in range ( i ) : NEW_LINE INDENT if ( envelopes [ i ] [ 0 ] > envelopes [ j ] [ 0 ] and envelopes [ i ] [ 1 ] > envelopes [ j ] [ 1 ] and dp [ i ] < dp [ j ] + 1 ) : NEW_LINE INDENT dp [ i ] = dp [ j ] + 1 NEW_LINE DEDENT DEDENT max_envelope = max ( max_envelope , dp [ i ] ) NEW_LINE DEDENT return max_envelope NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT envelopes = [ [ 4 , 3 ] , [ 5 , 3 ] , [ 5 , 6 ] , [ 1 , 2 ] ] NEW_LINE print ( maxEnvelopes ( envelopes ) ) NEW_LINE DEDENT