Users Online

· Guests Online: 107

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads
No Threads created
Hottest Threads
No Threads created

Latest Articles

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.

  1. #include <iostream>
  2. #include <string.h>
  3. #include <stdio.h>
  4.  
  5. using namespace std;
  6.  
  7. #define ARRAY_SIZE(A) sizeof(A)/sizeof(A[0])
  8. // Binary search (note boundaries in the caller)
  9. // A[] is ceilIndex in the caller
  10. int CeilIndex(int A[], int l, int r, int key)
  11. {
  12.     int m;
  13.  
  14.     while (r - l > 1)
  15.     {
  16.         m = l + (r - l) / 2;
  17.         (A[m] >= key ? r : l) = m; // ternary expression returns an l-value
  18.     }
  19.  
  20.     return r;
  21. }
  22.  
  23. int LongestIncreasingSubsequenceLength(int A[], int size)
  24. {
  25.     // Add boundary case, when array size is one
  26.  
  27.     int *tailTable = new int[size];
  28.     int len; // always points empty slot
  29.  
  30.     memset(tailTable, 0, sizeof(tailTable[0]) * size);
  31.  
  32.     tailTable[0] = A[0];
  33.     len = 1;
  34.     for (int i = 1; i < size; i++)
  35.     {
  36.         if (A[i] < tailTable[0])
  37.             // new smallest value
  38.             tailTable[0] = A[i];
  39.         else if (A[i] > tailTable[len - 1])
  40.             // A[i] wants to extend largest subsequence
  41.             tailTable[len++] = A[i];
  42.         else
  43.             // A[i] wants to be current end candidate of an existing subsequence
  44.             // It will replace ceil value in tailTable
  45.             tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];
  46.     }
  47.  
  48.     delete[] tailTable;
  49.  
  50.     return len;
  51. }
  52.  
  53. int main()
  54. {
  55.     int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
  56.     int n = ARRAY_SIZE(A);
  57.  
  58.     printf("Length of Longest Increasing Subsequence is %d\n",
  59.             LongestIncreasingSubsequenceLength(A, n));
  60.  
  61.     return 0;
  62. }

Output:

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

 

Comments

No Comments have been Posted.

Post Comment

Please Login to Post a Comment.

Ratings

Rating is available to Members only.

Please login or register to vote.

No Ratings have been Posted.
Render time: 0.82 seconds
10,259,021 unique visits