Maximum number of envelopes that can be put inside other bigger envelopes | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxEnvelopes ( vector < vector < int > > envelopes ) { int N = envelopes . size ( ) ; if ( N == 0 ) return N ; sort ( envelopes . begin ( ) , envelopes . end ( ) ) ; int dp [ N ] ; int max_envelope = 1 ; dp [ 0 ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) { dp [ i ] = 1 ; for ( int 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 = max ( max_envelope , dp [ i ] ) ; } return max_envelope ; } int main ( ) { vector < vector < int > > envelopes = { { 4 , 3 } , { 5 , 3 } , { 5 , 6 } , { 1 , 2 } } ; cout << maxEnvelopes ( envelopes ) ; return 0 ; }