Longest Increasing sub sequence

Problem: The problem is identify the longest increasing sub-sequence in an array of numbers.

The solution to the problem is to first find out all the increasing sequences less that the
current no and find out the max out of it. Add +1 to include the current no.

For ex: 2,7,3,4,9,8,12

For no of 9, there are two increasing sequences which are less than current no.

1)2,7
2)2,3,4

So the increasing seq count for 9 is 2,3,4,9 (count is 4).

So for the increasing seq is

LIS(i) = Max { LIS(j) } + 1 for 1<j<i and A[i]>A[j];
       = 1 if No such j

2,7,3,4,9,8,12

Following are increasing sub sequences:

LIS 1 : 2,7,9,12
LIS 2 : 2,3,4,9,12
LIS 3 : 2,3,4,8,12

Note : LIS for single element is 1, single element is increasing sequence.

C++ Program:

void LIS(int A[],int n)
{
int LIS[8];

for(int i=0;i<n;i++)
LIS[i]=1;

for(int i=0;i<n;i++)
{
        //For Each a[i], check if there are  is a
        //increasing seq, whose value is more than
        //the curent seq value.

        //We are checking for all the no which are
        //less than i.
    for(int j=0;j<i;j++)
    {
        if(A[i]>A[j] && LIS[i]<LIS[j]+1)
        {
            //IF you find a any no on the left side
            //of the current and
            LIS[i]=LIS[j]+1;
        }
    }
}

int max=0;
for(int i=0;i<n;i++)
if(LIS[i]>max)
max=LIS[i];

cout<<" Longest seq is :"<<max<<endl;
}