Largest subset of rectangles such that no rectangle fit in any other rectangle | C ++ 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 ; Driver code ; ( height , width ) pairs
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  10 NEW_LINE int dp [ N ] [ N ] ; int findLongest ( pair < int , int > a [ ] , int n , int present , int previous ) { if ( present == n ) { return 0 ; } else if ( previous != -1 ) { if ( dp [ present ] [ previous ] != -1 ) return dp [ present ] [ previous ] ; } int ans = 0 ; if ( previous == -1 ) { ans = 1 + findLongest ( a , n , present + 1 , present ) ; ans = max ( ans , findLongest ( a , n , present + 1 , previous ) ) ; } else { int h1 = a [ previous ] . first ; int h2 = a [ present ] . first ; int w1 = a [ previous ] . second ; int w2 = a [ present ] . second ; if ( ( h1 <= h2 && w1 <= w2 ) ) { ans = max ( ans , findLongest ( a , n , present + 1 , previous ) ) ; } else { ans = 1 + findLongest ( a , n , present + 1 , present ) ; ans = max ( ans , findLongest ( a , n , present + 1 , previous ) ) ; } } return dp [ present ] [ previous ] = ans ; } int getLongest ( pair < int , int > a [ ] , int n ) { memset ( dp , -1 , sizeof dp ) ; sort ( a , a + n ) ; int ans = findLongest ( a , n , 0 , -1 ) ; return ans ; } int main ( ) { pair < int , int > a [ ] = { { 1 , 5 } , { 2 , 4 } , { 1 , 1 } , { 3 , 3 } } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << getLongest ( a , n ) ; return 0 ; }