C++ Program to Find the Longest Increasing Subsequence

This is a C++ Program to implement LCS. The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.) It is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics.

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.

```
#include <iostream>
```
```
#include <string.h>
```
```
#include <stdio.h>
```
```
 
```
```
using namespace std;
```
```
 
```

#define ARRAY_SIZE(A) sizeof(A)/sizeof(A[0])

// Binary search (note boundaries in the caller)

```
// A[] is ceilIndex in the caller
```

int CeilIndex(int A[], int l, int r, int key)

```
{
```
```
    int m;
```
```
 
```
```
    while (r - l > 1)
```
```
    {
```
```
        m = l + (r - l) / 2;
```

        (A[m] >= key ? r : l) = m; // ternary expression returns an l-value

```
    }
```
```
 
```
```
    return r;
```
```
}
```
```
 
```

int LongestIncreasingSubsequenceLength(int A[], int size)

```
{
```

    // Add boundary case, when array size is one

```
 
```
```
    int *tailTable = new int[size];
```

    int len; // always points empty slot

```
 
```

    memset(tailTable, 0, sizeof(tailTable[0]) * size);

```
 
```
```
    tailTable[0] = A[0];
```
```
    len = 1;
```
```
    for (int i = 1; i < size; i++)
```
```
    {
```
```
        if (A[i] < tailTable[0])
```
```
            // new smallest value
```
```
            tailTable[0] = A[i];
```

        else if (A[i] > tailTable[len - 1])

            // A[i] wants to extend largest subsequence

```
            tailTable[len++] = A[i];
```
```
        else
```

            // A[i] wants to be current end candidate of an existing subsequence

            // It will replace ceil value in tailTable

            tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];

```
    }
```
```
 
```
```
    delete[] tailTable;
```
```
 
```
```
    return len;
```
```
}
```
```
 
```
```
int main()
```
```
{
```

    int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };

```
    int n = ARRAY_SIZE(A);
```
```
 
```

    printf("Length of Longest Increasing Subsequence is %d\n",

            LongestIncreasingSubsequenceLength(A, n));

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

Output:

$ g++ LCS.cpp
$ a.out
 
Length of Longest Increasing Subsequence is 6
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

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

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Implement Kadane’s Algorithm

» Next - C++ Program to Check Whether a Directed Graph Contains a Eulerian Cycle

Related Posts:

Recommended Articles: