Longest Increasing Subsequence using Longest Common Subsequence Algorithm | C ++ implementation of the approach ; Function to return the size of the longest increasing subsequence ; Create an 2D array of integer for tabulation ; Take the second sequence as the sorted sequence of the given sequence ; Classical Dynamic Programming algorithm for Longest Common Subsequence ; Return the ans ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LISusingLCS ( vector < int > & seq ) { int n = seq . size ( ) ; vector < vector < int > > L ( n + 1 , vector < int > ( n + 1 ) ) ; vector < int > sortedseq ( seq ) ; sort ( sortedseq . begin ( ) , sortedseq . end ( ) ) ; for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 j == 0 ) L [ i ] [ j ] = 0 ; else if ( seq [ i - 1 ] == sortedseq [ j - 1 ] ) L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 ; else L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) ; } } return L [ n ] [ n ] ; } int main ( ) { vector < int > sequence { 12 , 34 , 1 , 5 , 40 , 80 } ; cout << LISusingLCS ( sequence ) << endl ; return 0 ; }