In this problem (Longest Common Decreasing Subsequence), we are given 2 arrays and we need to find out the longest common decreasing subsequence from those two arrays. This can be solved using Dynamic Programming.

Let us first understand what do we mean by longest decreasing subsequence.

• A subsequence is a sequence in an array that occurs in the same relative order.

For example, if the array is [2,5,8,3,4,6] , then
[2,8,3] , [3,4,6] , [5,3,6]...etc are some subsequences of the array.

• We need to find the longest subsequence such that all the elements will be in decreasing order.

Consider an array: s1 = [9,7,3,5,1,2,4]
Therefore, for s1, longest decreasing subsequence = [9,7,3,1] or [9,7,5,2].. etc
The length of LDS = 4.

• What is longest common decreasing subsequence?

Given any 2 arrays, the length of the longest decreasing subsequence, that is present in both of them is the longest common decreasing subsequence.

For example:
arr1 = [8,3,7,2]
arr2 = [9,8,4,3,6,1,2]

Here, [8,3,2] is the longest subsequence that is decreasing and it is common in both the arrays.

Approach

We will be using Dynamic Programming to tackle this problem. We will use the following approach -

1. We have 2 arrays arr1[] and arr2[], where length of arr2[] will be greater than that of arr1[].
2. We will create one more array dp[] having same length as that of arr2[] and it will be initialised with zero.
3. For every element of arr1[], we will traverse through all the elements of arr2[]. Hence, we will use nested for loops. The outer loop will be for arr1[] and the inner loop will be for arr2[].
4. During the traversal, whenever we encounter common elements in arr1[] and arr2[], the max length of the common decreasing subsequence till then will be stored in the array dp[].
5. We will also use a variable "current" , which will assist in finding the value to be stored in dp[].
6. After the traversal is complete, we will find the maximum value from all the values in dp[] and that will be our final answer!

• Time complexity: O(N^2)

We will take a look at the approach with an example.

Code:

The following is the solution of the problem in C++:

// A C++ Program to find length of the Longest Common 
// Decreasing Subsequence (LCDS) 
#include<bits/stdc++.h> 
using namespace std; 

// Returns the length and the LCDS of two 
// arrays arr1[0..n-1] and arr2[0..m-1] 
int LCDS(int arr1[], int n, int arr2[], int m) 
{ 

	//When one or both the arrays are empty. 
	if(n==0 || m==0)
		return 0;


	// table[j] is going to store length of LCDS 
	// 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 LCDS 
		int current = 0; 

		// For each element of arr1[], traverse 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; 
} 

/* Driver program to test above function */
int main() 
{ 
	int arr1[] = {2, 4, 3, 1}; 
	int arr2[] = {2, 5, 8, 4, 3, 0, 1}; 

	int n = sizeof(arr1)/sizeof(arr1[0]); 
	int m = sizeof(arr2)/sizeof(arr2[0]); 

	cout<< "Length of LCDS is "
		<< LCDS(arr1, n, arr2, m); 
	return (0); 
} 

Output:

Length of LCDS is 3

Workflow:

Let us walkthrough the problem with the given example:

arr1 = [2, 4, 3, 1]
arr2 = [2, 5, 8, 4, 3, 0, 1]

Initially, dp = [0, 0, 0, 0, 0, 0, 0]

Let's start traversing through the arrays:

• when i=0 and j=0 ,current=0 and arr1[0] = arr2[0] = 2
  Therefore, dp[] will be updated to [1, 0, 0, 0, 0, 0, 0].
  arr2[] is then traversed completely for i=0, whith no other changes.

• when i=1 and j=3, current=0 and arr1[1] = arr2[3] = 4
  Hence, again dp[] will change. But here, as there is no decreasing sequence till now, dp[] will again have a "1" inserted in it in 3rd position. dp[] = [1, 0, 0, 1, 0, 0, 0].

• when i=2 and j=3, arr1[2] < arr2[3] i.e 3 < 4. Also, dp[3] = 1.
  Here we observe a common decreasing sequence from 4 to 3. Hence, current = 1. And then current + 1 i.e 2 will be later stored in dp[4] when i=2 and j=4.

• Similarly, when we encounter the last element i.e. "1" in the arrays, we will observe common decreasing sequence from 4 to 3 to 1. Hence, current = 2, and current + 1 i.e 3 will be stored in dp[6].

This procedure is repeated throughout the whole traversal and final dp[] = [1, 0, 0, 1, 2, 0, 3]

We will take the maximum value from this array.
Since 3 is the largest value, our final answer will be 3.

Therefore, the length of the longest common decreasing subsequence for arr1[] and arr2[] is 3.

Complexity

• Time complexity : O(l1 * l2) , since for each element of arr1[] we traverse the entire arr2[].
• Space complexity : O(l2) , as we use an array dp[] having length of arr2[] to store LCDS.