C++ Programming Code Examples C++ > Strings Code Examples Find the Longest Increasing Subsequence of a Given Sequence Find the Longest Increasing Subsequence of a Given Sequence 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. #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; }