# Maximum number of plates that can be placed from top to bottom in increasing order of size

Maximum number of plates that can be placed from top to bottom in increasing order of sizeGiven a 2D array plates[][] of size N, which each row representing the length and width of a N rectangular plates, the task is to find the maximum number of plates that can be placed on one another. Note: A plate can be put on another only if its length and width are strictly smaller than that plate. Examples:Input: Plates[][] = [ [3, 5], [6, 7], [7, 2], [2, 3] ]Output: 3Explanation: Plates can be arranged in this manner [ 6, 7 ] => [ 3, 5 ] => [ 2, 3 ].Input: Plates[][] = [ [6, 4], [ 5, 7 ], [1, 2], [ 3, 3 ], [ 7, 9 ] ]Output: 4Explanation: Plates can be arranged in this manner [ 7, 9 ] => [ 5, 7 ] => [ 3, 3 ] => [ 1, 2 ].Approach: The problem is a variation of the Longest increasing subsequence problem. The only difference is that in LIS, if i < j, then ithelement will always come before the jth element. But here, choosing of plates doesn’t depend on index. So, to get this index restriction, sorting all the plates in decreasing order of area is required.If (i < j) and area of ithplate is also greater than jthplate, then ithplate will always come before(down) the jth plate.Recursive approach:Two possible choices exists for each plate, i.e. either to include it in the sequence or discard it. A plate can be included only when its length and width are smaller than the previous included plate.Recursion tree for the array plates[][] = [ [6, 7], [3, 5], [7, 2] ] is as follows: Below is the implementation of the recursive approach:C++  #include using namespace std;  bool comp(vector v1,          vector v2){    return v1[0] * v1[1] > v2[0] * v2[1];}  int countPlates(vector& plates,                int lastLength, int lastWidth,                int i, int n){        if (i == n)        return 0;      int taken = 0, notTaken = 0;              if (lastLength > plates[i][0]        && lastWidth > plates[i][1]) {                  taken = 1 + countPlates(plates, plates[i][0],                                plates[i][1], i + 1, n);                  notTaken = countPlates(plates, lastLength,                               lastWidth, i + 1, n);    }          else                  notTaken = countPlates(plates, lastLength,                               lastWidth, i + 1, n);      return max(taken, notTaken);}  int main(){    vector plates = { { 6, 4 }, { 5, 7 },                         { 1, 2 }, { 3, 3 }, { 7, 9 } };    int n = plates.size();          sort(plates.begin(), plates.end(), comp);          int lastLength = INT_MAX;    int lastWidth = INT_MAX;      cout v2[0] * v2[1];}  int countPlates(vector& plates, int n){              int maximum_plates = 1;    vector 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 plates = { { 6, 4 }, { 5, 7 },                         { 1, 2 }, { 3, 3 }, { 7, 9 } };    int n = plates.size();          sort(plates.begin(), plates.end(), comp);      cout