Largest subset of rectangles such that no rectangle fit in any other rectangle | JavaScript implementation of the approach ; Recursive function to get the largest subset ; Base case when it exceeds ; If the state has been visited previously ; Initialize ; No elements in subset yet ; First state which includes current index ; Second state which does not include current index ; If the rectangle fits in , then do not include the current index in subset ; First state which includes current index ; Second state which does not include current index ; Function to get the largest subset ; Initialize the DP table with - 1 ; Sort the array ; Get the answer ; ( height , width ) pairs
var N = 10 ; var dp = Array . from ( Array ( N ) , ( ) => Array ( N ) . fill ( - 1 ) ) ; function findLongest ( a , n , present , previous ) { if ( present == n ) { return 0 ; } else if ( previous != - 1 ) { if ( dp [ present ] [ previous ] != - 1 ) return dp [ present ] [ previous ] ; } var ans = 0 ; if ( previous == - 1 ) { ans = 1 + findLongest ( a , n , present + 1 , present ) ; ans = Math . max ( ans , findLongest ( a , n , present + 1 , previous ) ) ; } else { var h1 = a [ previous ] [ 0 ] ; var h2 = a [ present ] [ 0 ] ; var w1 = a [ previous ] [ 1 ] ; var w2 = a [ present ] [ 1 ] ; if ( ( h1 <= h2 && w1 <= w2 ) ) { ans = Math . max ( ans , findLongest ( a , n , present + 1 , previous ) ) ; } else { ans = 1 + findLongest ( a , n , present + 1 , present ) ; ans = Math . max ( ans , findLongest ( a , n , present + 1 , previous ) ) ; } } return dp [ present ] [ previous ] = ans ; } function getLongest ( a , n ) { dp = Array . from ( Array ( N ) , ( ) => Array ( N ) . fill ( - 1 ) ) ; a . sort ( ( a , b ) => a - b ) ; var ans = findLongest ( a , n , 0 , - 1 ) ; return ans ; } var a = [ [ 1 , 5 ] , [ 2 , 4 ] , [ 1 , 1 ] , [ 3 , 3 ] ] ; var n = a . length ; document . write ( getLongest ( a , n ) ) ;