text: Longest Common Increasing Subsequence ( LCS + LIS ) | A C ++ Program to find length of the Longest Common Increasing Subsequence ( LCIS ) ; Returns the length and the LCIS of two arrays arr1 [ 0. . n - 1 ] and arr2 [ 0. . m - 1 ] ; table [ j ] is going to store length of LCIS ending with arr2 [ j ] . We initialize it as 0 , ; Traverse all elements of arr1 [ ] ; Initialize current length of LCIS ; For each element of arr1 [ ] , traverse all elements of arr2 [ ] . ; If both the array have same elements . Note that we don 't break the loop here. ; Now seek for previous smaller common element for current element of arr1 ; The maximum value in table [ ] is out result ; Driver program to test above function
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int LCIS ( int arr1 [ ] , int n , int arr2 [ ] , int m ) { int table [ m ] ; for ( int j = 0 ; j < m ; j ++ ) table [ j ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int current = 0 ; for ( int j = 0 ; j < m ; j ++ ) { if ( arr1 [ i ] == arr2 [ j ] ) if ( current + 1 > table [ j ] ) table [ j ] = current + 1 ; if ( arr1 [ i ] > arr2 [ j ] ) if ( table [ j ] > current ) current = table [ j ] ; } } int result = 0 ; for ( int i = 0 ; i < m ; i ++ ) if ( table [ i ] > result ) result = table [ i ] ; return result ; } int main ( ) { int arr1 [ ] = { 3 , 4 , 9 , 1 } ; int arr2 [ ] = { 5 , 3 , 8 , 9 , 10 , 2 , 1 } ; int n = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ] ) ; int m = sizeof ( arr2 ) / sizeof ( arr2 [ 0 ] ) ; cout << " Length ▁ of ▁ LCIS ▁ is ▁ " << LCIS ( arr1 , n , arr2 , m ) ; return ( 0 ) ; }