Today we review longest common subsequence instead of longest increasing subsequence
The LCS is based on the optimal substructure as follows: X, Y are sequences and Z is the LCS
1. if xm = yn, then zk = xm = yn and Zk-1 is the LCS of Xm-1 and Yn-1
2. if xm <> yn, then zk <> xm implies that Z is an LCS of Xm-1 and Y.
3. if xm <> yn, then zk <> yn, implies that Z is an LCS of X and Yn-1

The length of the longest common subsequence c[i,j] is :
1. 0 if i = 0 or j = 0
2. c[i-1, j-1] + 1 if i,j > 0 and xi = yj
3. max(c[i,j-1], c[i-1, j]) if i, j  > 0 and xi != yj

LCS-Length(x, y)
m <- length(x)
n<-length(y)
for i = 1 to m
     c[i, 0] = 0
for j = 0 to n
     c[0,j] = 0
for i = 1 to m
      for j = 1 to n
            if xi == yi
               c[i,j] = c[i -1, j-1] + 1
               b[i,j] = up-left
            elseif c[i-1,j]  >= c[i, j-1]
               c[i,j] = c[i-1, j]
               b[i,j] = up
            else c[i,j] = c[i,j-1]
               b[i,j] = left
return c and b
Now the LCS can be printed with :
PRINT-LCS( b, X, i, j) // PRINT-LCS(b, X, length(X), length(Y))
if i = 0 or j = 0
     then return
if b[i,j] == up-left
     then PRINT-LCS (b, X, i-1, j-1)
             print xi
else if b[i,j] == up
           then PRINT-LCS(b,X,i-1,j)
else PRINT-LCS(b,X, i, j-1)

It can be hard to choose between longest common subsequence and longest increasing subsequence as a solution to a problem. For example, consider the box stacking problem where boxes of different l x b x h exist and we have to stack them up such that we can find the tallest tower

Previously in our earlier blog post we incorrectly referred to it as the longest common subsequence but it is in fact longest increasing subsequence for the formation of the tower.

The solution remains the same:
var msh = new List<int>();
for (int i = 1; i < = n; i++)
   for (int j = 0; j < i; j++)
    {
                if (w (j)*l(j) > w (i)*l (i) && max (msh [j] + 1) > msh (i)
                MSH (i) = msh[j] + 1;
    }
return msh.max();

while dynamic programming considers choices repeatedly, back tracking never considers an invalid option and reduces the number of options from the permutations.