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.

/* A Naive recursive implementation of LCS problem */

```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
 
```
```
int max(int a, int b);
```
```
 
```

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */

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));

```
}
```
```
 
```

/* Utility function to get max of 2 integers */

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

/* Driver program to test above function */

```
int main() {
```
```
    char X[] = "AGGTAB";
```
```
    char Y[] = "GXTXAYB";
```
```
 
```
```
    int m = strlen(X);
```
```
    int n = strlen(Y);
```
```
 
```

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

```
 
```
```
    return 0;
```
```
}
```

Output:

$ gcc LCS.c
$ ./a.out
 
Length of LCS is 4

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

« Prev - C Program to Implement Grep, Egrep and Fgrep Commands

» Next - C Program to Implement the Monoalphabetic Cipher

Related Posts:

Recommended Articles: