PHP-Fusion Powered Website - Articles: C++ Program to Find the Longest Increasing Subsequence

Users Online

· Guests Online: 39

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » C++ Program to Find the Longest Increasing Subsequence

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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

C++ Program to Find the Longest Increasing Subsequence

C++ Program to Find the Longest Increasing Subsequence

Comments

Post Comment

Ratings