Today we review another coding problem
Problem: There are a lot of cuboid boxes of arbitrary sizes.  Find the largest subset of cubes that can fit into each other.
Solution: This problem can be simplified if we think about cubes. Cubes can fit into each other based on their sorted edges.. This reminds us of a longest increasing subsequence (LIS) problem.
We recall the solution of the LIS problem as :
x can be a single-element increasing sequence or
x can be appended at the end of the longest increasing subsequence ending at some y provided that y precedes x and y < x
For example, 
Edges          11, 1, 10,  4, 3, 2, 8, 7, 12, 6, 9, 5
Length of     1   1    2   2  2  2  3  3   4   3  4, 3
subsequence
This we can now code as :
int getLIS(List<int> cubeedges)
{
var lis = new List<int>();
for (int i = 0; i < cubeedges.Count(); i++)
{
 for (int j = 0; j < i; j ++)
  {
      if (cubeedges[j] < cubeedges[i] && lis[j] + 1 > lis[i])
                     lis[i] = lis[j] + 1;
   }
}
return list.max();
}
The above is O(N^2). We can have  a O( N LogN ) solution also
Formally,
Let X[i] represent the sequence 2, 3, 1
Let M[j] store the index k of the smallest value X[k] so that there is an increasing subsequence of length j ending at X[k] on the range k <=i and j <=k <= i.  j represents the length of the increasing subsequence and k represents the index of termination.
and Let P[k] store the index predecessor of X[k]
The longest Increasing subsequence  at any given point is given by X [M [1]], X [M [2]], ... X [M [L]] and if there is an increasing subsequence at i then there is one at i-1 which is X [P [M[i]]] and between these two bounds we can do a logarithmic search for j <=k <= i
Therefore the steps are:
P = array of length N  - all initialized to zero
M = array of length N + 1 // pad on the left so that we can use zero based index.
L = 0
for i in range 0 to N-1:
      Binary search for the largest positive j <= L
      such that X[M[j]] < X[i]
      lo = 1
      hi = L
      Binary Search between lo and hi adjusts lo and hi
      After searching lo is 1 greater than the length of the longest prefix
      newL = lo
      The predecessor of X[i] is the last index of the subsequence of length newL-1
      P[i] = M[newL -1]
      M[newL] = i
      if newL > L:
          if we found a subsequence longer than L, update L
          L = newL

   // Reconstruct the longest increasing subsequence
T = array of length L
k = M[L]
for i in range L-1 to 0:
    T[i] = X[k]
     k = P[k]

return T
The only difference between cubes and cuboids is that we compare not one dimension but all three.

This means that all the edges in one must be smaller than the corresponding of the other