Question: You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other.

For example:
If Box A has LBH as 7 8 9
If Box B has LBH as 5 6 8
If Box C has LBH as 5 8 7
If Box D has LBH as 4 4 4

then answer is A,B,D

A box can fit into another only and only if all dimensions of that is less than the bigger box. Also Rotation of boxes is not possible.

Solution: To find the the longest increasing sequence, we maintain a lookup table, where the ith location indicates the maximum increasing value, for that input.

extending this idea to the current problem. given input is :

{7,8,9},{5,6,8},{5,8,7},{4,4,4}.

the lookup table for this problem should hold at each ith location, the maximum number of boxes that can be filled for the ith input.

to ease the computation we sort (descending) input array with one of the dimensions ( in this case the input is already sorted by length.

formula

Sj= max(Sk)+1 where 0<=k
example:
A - {7,8,9}
B - {5,6,8}
C - {5,8,7}
D - {4,4,4}

0 A B C D
S 0 1 2 2 3

so 3 is the max. # of boxes that can be filled.