Given two arrays, arr1[] and arr2[] of sizes M and N respectively, find the length of the longest common increasing subsequence(LCIS). 
Example 1:
Input:
M = 4
Arr1[] = {3, 4, 9, 1}
N = 7
Arr2[] = {5, 3, 8, 9, 10, 2, 1}
Output: 2
Explanation: The longest increasing subsequence
that is common is {3, 9} and its length is 2.
Example 2:
Input:
M = 4
Arr1[] = {1, 1, 4, 3}
N = 4
Arr2[] = {1, 1, 3, 4}
Output: 2
Explanation: There are two common 
subsequences {1, 4} and {1, 3}
both of length 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function LCIS() which takes arr1[] and its size m, arr2[] and its size n as input parameters and returns length of LCIS.
 
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 <= M, N <= 10^{3}
1 <= Arr1[i], Arr2[i] <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def LCIS(self, arr1, m, arr2, n):
        # code here

Solutions:
class Solution:

	def LCIS(self, arr1, n, arr2, m):
		table = [0] * m
		for j in range(m):
			table[j] = 0
		for i in range(n):
			current = 0
			for j in range(m):
				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]
		result = 0
		for i in range(m):
			if table[i] > result:
				result = table[i]
		return result


class Solution:

	def LCIS(self, arr1, m, arr2, n):
		table = [0] * n
		for i in range(m):
			cur = 0
			for j in range(n):
				if arr1[i] == arr2[j]:
					table[j] = cur + 1
				elif arr1[i] > arr2[j]:
					cur = max(cur, table[j])
		return max(table)


import array

class Solution:

	def LCIS(self, a, m, b, n):
		temp = array.array('i', [0] * (len(b) + 1))
		for i in range(m):
			prev = 0
			for j in range(n):
				if a[i] == b[j]:
					temp[j + 1] = prev + 1
				if a[i] > b[j]:
					prev = max(prev, temp[j + 1])
		return max(temp)


class Solution:

	def LCIS(self, a, m, b, n):
		max_len = [0] * n
		highest = 0
		for i in range(m):
			count = 0
			for j in range(n):
				if a[i] == b[j]:
					max_len[j] = max(count + 1, max_len[j])
					highest = max(max_len[j], highest)
				elif a[i] > b[j]:
					count = max(max_len[j], count)
		return highest


class Solution:

	def remove_irrelevant_elements(self, lst1, lst2):
		return [x for x in lst1 if x in lst2]

	def LCIS(self, a, m, b, n):
		a = self.remove_irrelevant_elements(a, b)
		b = self.remove_irrelevant_elements(b, a)
		(n, m) = (len(a), len(b))
		max_len = [0] * m
		highest = 0
		for i in range(n):
			count = 0
			for j in range(m):
				if a[i] == b[j]:
					max_len[j] = max(count + 1, max_len[j])
					highest = max(max_len[j], highest)
				elif a[i] > b[j]:
					count = max(max_len[j], count)
		return highest


class Solution:

	def LCIS(self, arr1, m, arr2, n):
		table = [0] * n
		res = 0
		for i in range(m):
			count = 0
			for j in range(n):
				if arr1[i] > arr2[j]:
					count = max(count, table[j])
				if arr1[i] == arr2[j]:
					table[j] = max(table[j], count + 1)
					res = max(table[j], res)
		return res


class Solution:

	def LCIS(self, arr1, m, arr2, n):
		dp = [0] * n
		for i in range(m):
			curr = 0
			for j in range(n):
				if arr1[i] == arr2[j]:
					dp[j] = max(dp[j], curr + 1)
				elif arr1[i] > arr2[j]:
					curr = max(curr, dp[j])
		return max(dp)


class Solution:

	def LCIS(self, arr1, m, arr2, n):
		t = [0] * n
		for i in range(m):
			c = 0
			for j in range(n):
				if arr1[i] == arr2[j]:
					if c + 1 > t[j]:
						t[j] = c + 1
				if arr1[i] > arr2[j]:
					if t[j] > c:
						c = t[j]
		return max(t)


class Solution:

	def LCIS(self, A, m, B, n):
		dp = [0] * n
		for i in range(m):
			c = 0
			for j in range(n):
				if A[i] == B[j]:
					dp[j] = max(dp[j], c + 1)
				if A[i] > B[j]:
					c = max(c, dp[j])
		return max(dp)


class Solution:

	def LCIS(self, arr1, m, arr2, n):
		dp = [0] * m
		for i in range(n):
			counter = 0
			for j in range(m):
				if arr1[j] == arr2[i] and counter + 1 > dp[j]:
					dp[j] = counter + 1
				if arr2[i] > arr1[j] and counter < dp[j]:
					counter = dp[j]
		return max(dp)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		m = int(input())
		arr1 = list(map(int, input().strip().split()))
		n = int(input())
		arr2 = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.LCIS(arr1, m, arr2, n)
		print(ans)
		tc -= 1


class Solution:

	def LCIS(self, arr1, m, arr2, n):
		store = [0 for i in range(n)]
		ans = 0
		for i in range(m):
			curr = 0
			for j in range(n):
				if arr1[i] == arr2[j]:
					if curr + 1 > store[j]:
						store[j] = curr + 1
				if arr1[i] > arr2[j]:
					if curr < store[j]:
						curr = store[j]
		for i in range(n):
			if store[i] > ans:
				ans = store[i]
		return ans


class Solution:

	def LCIS(self, arr1, m, arr2, n):
		table = [0 for i in range(n)]
		for i in range(m):
			current = 0
			for j in range(n):
				if arr1[i] == arr2[j] and current + 1 > table[j]:
					table[j] = current + 1
				if arr1[i] > arr2[j] and table[j] > current:
					current = table[j]
		res = max((x for x in table))
		return res