#include<stdio.h>
#include<bits/stdc++.h>




int llis(char arr[],int n, int *max)
{

	if (n == 1)
		return 1;


	int r;
        int loflis = 1;


	for (int i = 1; i < n; i++)
	{
		r = llis(arr, i, max);
		if (arr[i-1] < arr[n-1] && r + 1 > loflis)
			loflis = r + 1;
	}


	if (*max < loflis)
	*max = loflis;


	return loflis;
}

int lis(char arr[], int n)
{

	int max = 1;


	llis( arr, n, &max );


	return max;
}

int max(int a, int b)
{
	return (a > b)? a : b;
}


int lcs( char *X, char *Y, int m, int n )
{
if (m == 0 || n == 0)
	return 0;
if (X[m-1] == Y[n-1])
	return 1 + lcs(X, Y, m-1, n-1);
else
	return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}


int main()
{
	char arr[] = { 1, 2, 1, 3, 9, 5, 4, 9, 10 };
        char arr1[]={ 'A', 'B', 'C', 'I', 'X', 'P'};

        int n = sizeof(arr)/sizeof(arr[0]);

	printf("lis length is of arr : %d\n",lis( arr, n ));
        printf("lis length is of arr1 : %d\n",lis( arr1, n ));




        char X[] = "AGGTAB";
        char Y[] = "GXTXAYB";

        int m = strlen(X);
        int k = strlen(Y);

        printf("Length of LCS is %d \n", lcs( X, Y, m, k ) );
  return 0;
}