## Monday, June 20, 2016

### Longest Common Increasing Subsequence (LCS + LIS) - GeeksforGeeks

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)
`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.
`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;`
`}`
Read full article from Longest Common Increasing Subsequence (LCS + LIS) - GeeksforGeeks