# C Program to Find the Longest Increasing Subsequence

«
»
This is a C Program to find length Longest Commmon Subsequence of a given sequence. LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Here is source code of the C Program to Find the Longest Increasing Subsequence of a Given Sequence. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/* A Naive recursive implementation of LCS problem */`
2. `#include<stdio.h>`
3. `#include<stdlib.h>`
4. ` `
5. `int max(int a, int b);`
6. ` `
7. `/* Returns length of LCS for X[0..m-1], Y[0..n-1] */`
8. `int lcs(char *X, char *Y, int m, int n) {`
9. `    if (m == 0 || n == 0)`
10. `        return 0;`
11. `    if (X[m - 1] == Y[n - 1])`
12. `        return 1 + lcs(X, Y, m - 1, n - 1);`
13. `    else`
14. `        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));`
15. `}`
16. ` `
17. `/* Utility function to get max of 2 integers */`
18. `int max(int a, int b) {`
19. `    return (a > b) ? a : b;`
20. `}`
21. ` `
22. `/* Driver program to test above function */`
23. `int main() {`
24. `    char X[] = "AGGTAB";`
25. `    char Y[] = "GXTXAYB";`
26. ` `
27. `    int m = strlen(X);`
28. `    int n = strlen(Y);`
29. ` `
30. `    printf("Length of LCS is %d\n", lcs(X, Y, m, n));`
31. ` `
32. `    return 0;`
33. `}`

Output:

```\$ gcc LCS.c
\$ ./a.out

Length of LCS is 4```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 