Maximum number of plates that can be placed from top to bottom in increasing order of size | C ++ Program for the above approach ; Comparator function to sort plates in decreasing order of area ; Function to count and return the max number of plates that can be placed ; Stores the maximum number of plates ; For each i - th plate , traverse all the previous plates ; If i - th plate is smaller than j - th plate ; Include the j - th plate only if current count exceeds the previously stored count ; Update the maximum count ; Driver code ; Sorting plates in decreasing order of area
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool comp ( vector < int > v1 , vector < int > v2 ) { return v1 [ 0 ] * v1 [ 1 ] > v2 [ 0 ] * v2 [ 1 ] ; } int countPlates ( vector < vector < int > > & plates , int n ) { int maximum_plates = 1 ; vector < int > dp ( n , 1 ) ; for ( int i = 1 ; i < n ; i ++ ) { int cur = dp [ i ] ; for ( int j = i - 1 ; j >= 0 ; j -- ) { if ( plates [ i ] [ 0 ] < plates [ j ] [ 0 ] && plates [ i ] [ 1 ] < plates [ j ] [ 1 ] ) { if ( cur + dp [ j ] > dp [ i ] ) { dp [ i ] = cur + dp [ j ] ; maximum_plates = max ( maximum_plates , dp [ i ] ) ; } } } } return maximum_plates ; } int main ( ) { vector < vector < int > > plates = { { 6 , 4 } , { 5 , 7 } , { 1 , 2 } , { 3 , 3 } , { 7 , 9 } } ; int n = plates . size ( ) ; sort ( plates . begin ( ) , plates . end ( ) , comp ) ; cout << countPlates ( plates , n ) ; return 0 ; }