Longest Common Increasing Subsequence (LCS + LIS) - GeeksforGeeks
Given two arrays, find length of the longest common increasing subsequence [LCIS] and print one of such sequences (multiple sequences may exist)
Suppose we consider two arrays –
arr1[] = {3, 4, 9, 1} and
arr2[] = {5, 3, 8, 9, 10, 2, 1}
Our answer would be {3, 9} as this is the longest common subsequence which is increasing also.
Read full article from Longest Common Increasing Subsequence (LCS + LIS) - GeeksforGeeks
Given two arrays, find length of the longest common increasing subsequence [LCIS] and print one of such sequences (multiple sequences may exist)
Suppose we consider two arrays –
arr1[] = {3, 4, 9, 1} and
arr2[] = {5, 3, 8, 9, 10, 2, 1}
Our answer would be {3, 9} as this is the longest common subsequence which is increasing also.
The idea is to use dynamic programming here as well. We store the longest common increasing sub-sequence ending at each index of arr2[]. We create an auxiliary array table[] such that table[j] stores length of LCIS ending with arr2[j]. At the end, we return maximum value from this table. For filling values in this table, we traverse all elements of arr1[] and for every element arr1[i], we traverse all elements of arr2[]. If we find a match, we update table[j] with length of current LCIS. To maintain current LCIS, we keep checking valid table[j] values.
Time Complexity : O(m*n)
Auxiliary Space : O(m)
Auxiliary Space : O(m)
int LCIS(int arr1[], int n, int arr2[], int m){ // table[j] is going to store length of LCIS // ending with arr2[j]. We initialize it as 0, int table[m]; for (int j=0; j<m; j++) table[j] = 0; // Traverse all elements of arr1[] for (int i=0; i<n; i++) { // Initialize current length of LCIS int current = 0; // For each element of arr1[], trvarse all // elements of arr2[]. for (int j=0; j<m; j++) { // If both the array have same elements. // Note that we don't break the loop here. if (arr1[i] == arr2[j]) if (current + 1 > table[j]) table[j] = current + 1; /* Now seek for previous smaller common element for current element of arr1 */ if (arr1[i] > arr2[j]) if (table[j] > current) current = table[j]; } } // The maximum value in table[] is out result int result = 0; for (int i=0; i<m; i++) if (table[i] > result) result = table[i]; return result;}
How to print a LCIS?
To print the longest common increasing subsequence we keep track of the parent of each element in the longest common increasing subsequence.
To print the longest common increasing subsequence we keep track of the parent of each element in the longest common increasing subsequence.
int LCIS(int arr1[], int n, int arr2[], int m){ // table[j] is going to store length of LCIS // ending with arr2[j]. We initialize it as 0, int table[m], parent[m]; for (int j=0; j<m; j++) table[j] = 0; // Traverse all elements of arr1[] for (int i=0; i<n; i++) { // Initialize current length of LCIS int current = 0, last = -1; // For each element of arr1[], trvarse all // elements of arr2[]. for (int j=0; j<m; j++) { // If both the array have same elements. // Note that we don't break the loop here. if (arr1[i] == arr2[j]) { if (current + 1 > table[j]) { table[j] = current + 1; parent[j] = last; } } /* Now seek for previous smaller common element for current element of arr1 */ if (arr1[i] > arr2[j]) { if (table[j] > current) { current = table[j]; last = j; } } } } // The maximum value in table[] is out result int result = 0, index = -1; for (int i=0; i<m; i++) { if (table[i] > result) { result = table[i]; index = i; } } // LCIS is going to store elements of LCIS int lcis[result]; for (int i=0; index != -1; i++) { lcis[i] = arr2[index]; index = parent[index]; } cout << "The LCIS is : "; for (int i=result-1; i>=0; i--) printf ("%d ", lcis[i]); return result;}