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 Reference Books in C++ Programming, Data Structures and Algorithms.