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:

advertisement
$ 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!
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.