The problem we will solve is that, given two arrays of intergers, we need to find the Longest common increasing subsequence from those arrays and print it. This problem can solved efficiently using Dynamic Programming.

Before solving it, we must have some knowledge of :

• What is Longest Common Subsequence ?

Given two sequences, the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “acd”, “bde”, .. etc are subsequences of “abcde”.

• What is Longest Increasing Subsequence ?

Given an array, the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {1,2,6,4,3,7,5} is 4 and LIS is {1,2,6,7}.

We will solve this using two approaches:

• Brute force approach O(N * 2^N) time
• Dynamic Programming approach O(N^2) time

Problem

You are given two arrays, find the longest common increasing subsequence.

Given arrays :
a1 = {2,6,4,9}
a2 = {3,4,2,7,9,6}

The answer would be {2, 9} as this is the longest common subsequence which is also increasing.

Approach

One approach can be the brute force approach, where we compare each element one by one and store all, common subsequence to find the increasing one. But that would neither be time efficient nor space efficient.

The steps in a brute force approach will be:

• Generate all subsequence of a given list
• For each subsequence, check if it exists in the other list and if it is in increasing order.

There are 2^N subsequences and to check if a subsequence is valid, it will take O(N) time. Hence, the time complexity of brute force approach will be O(N * 2^N) time. The space complexity will be O(1).

So, the better approach would be to use to Dynamic Programming.

We store the longest common increasing sub-sequence ending at each index of a2[]. We create an auxiliary array dp[] such that dp[j] stores length of Longest common increasing subsequence or LCIS ending with a2[j]. At the end, we return maximum value from this array.

dp[j] = length of Longest common increasing subsequence

For filling values in this dp array, we traverse all elements of a1[] and for every element in a1[i], we traverse all elements of a2[].
If we find a match, we update dp[j] with length of current LCIS. To maintain current LCIS, we keep checking valid dp[j] values.

# if a common element is found in both arrays
if arr1[i] == arr2[j]:
    dp[j] = max(current+1, dp[j])

# if arr1 element is greater, current variable is updated
if arr1[i] > arr2[j]:
    current = max(current, dp[j])

The maximum value in dp[] array is our answer.

Pseudocode

• Creating a dp table of length same as arr2 and elements as 0.
• Start traversing all elements of arr2 for each element of arr1.
• If a common element is found, current variable is incremented and is stored in dp array.
• If element of arr1 is greater than element of arr2, we update our current variable with the maximum of current or the value stored in dp at that index.
• After all elements of arr1 is covered, we return the maximum value from our dp table as result.

Implementation in Python

Following is the implementation of our above algorithm in Python:

# defining our answer function that return result
def answer(arr1, arr2):
    l1 = len(arr1)
    l2 = len(arr2)
    
    # creating our dp table that will store the length of LCIS ending at arr2[j]
    dp = [0]*l2
    
    # traversing all elements of arr1
    for i in range(l1):
        
        # variable to store length of current LCIS
        current = 0
        
        # traversing all elements of arr2
        for j in range(l2):
            
            # if a common element is found in both arrays
            if arr1[i] == arr2[j]:
                dp[j] = max(current+1, dp[j])
            
            # if arr1 element is greater, current variable is updated
            if arr1[i] > arr2[j]:
                current = max(current, dp[j])
    
    # final result for LCIS
    result = max(dp)
    return result
    
a1 = [2, 4, 9, 1] 
a2 = [2, 5, 8, 4, 9, 0, 1]

print("Length of LCIS is :",answer(a1, a2))

Workflow of solution

• Suppose we give our arr1 as [2,4,9,1] and arr2 as [2,5,8,4,9,0,1] to our answer funtion.
• Length of both arrays are taken in l1 and l2 variables as l1 = 4 and l2 = 7.
• An array with elements as 0 and length same as l2 is declared. Our dp array will look like : [0,0,0,0,0,0,0]
• We start traversing all elements of arr2 for each element of arr1.
• When we find a common element, we update our dp table at that index and if we find arr1 element greater than arr2 element, we update out current variable accordingly.
• After traversing first element of arr1, and all elements of arr2, our dp table will look like : [1,0,0,0,0,0,0] as first element of both arrays were common and current variable at that time was 0.
• Similarly, for all elements of arr1, exact process is repeated, our dp table at end would like : [1,0,0,2,3,0,1].
• At end, maximum value from this dp table is returned by function as our LCIS=3.

Complexity

• As we traverse all elements of arr2 for each element of arr1, our time complexity would be O(l1 * l2).
• For storing all LCIS for each element of arr2, we created an array of size l2, so our space complexity would be O(l2).

With this article at OpenGenus, you have the complete idea of solving this problem using Dynamic Programming. Enjoy.