Maximum number of envelopes that can be put inside other bigger envelopes | Java 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
import java . util . * ; import java . lang . * ; class GFG { static int maxEnvelopes ( int [ ] [ ] envelopes ) { int N = envelopes . length ; if ( N == 0 ) return N ; Arrays . sort ( envelopes , ( a , b ) -> ( a [ 0 ] != b [ 0 ] ) ? a [ 0 ] - b [ 0 ] : a [ 1 ] - b [ 1 ] ) ; int [ ] dp = new int [ 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 = Math . max ( max_envelope , dp [ i ] ) ; } return max_envelope ; } public static void main ( String [ ] args ) { int [ ] [ ] envelopes = { { 4 , 3 } , { 5 , 3 } , { 5 , 6 } , { 1 , 2 } } ; System . out . println ( maxEnvelopes ( envelopes ) ) ; } }