Read problems statements in Mandarin Chinese and Russian as well. 

There are N cards placed in a row, where every card has two numbers written on it, one on the top and 
one on the bottom. The numbers are between 1 and N (both inclusive). Every number is written on the top of exactly one card, and on the bottom of exactly one card as well.

Chef wants to rearrange the cards, such that the length of the longest common contiguous subsequence between the sequence formed by number written on top of the cards, and that formed by those written on the bottom is maximum. He can't modify the numbers written on any card and can't flip the cards, that is, for any card the number written on top remains at the top and the number written on bottom stays at the bottom. Find out the maximum possible length of the common contiguous subsequence.

------ Input ------ 

The first line of input contains an integer T denoting the number of test cases. 

The first line of each test
case contains an integer N.
The next line contains N space separated  integers A_{1},  A_{2}, ... , A_{N}, where A_{i}(1 ≤ i ≤ N) is the number written on the top of the i-th card.
The next line contains N space separated  integers B_{1},  B_{2}, ... , B_{N}, where B_{i}(1 ≤ i ≤ N) is the number written at the bottom of the  i-th card. 

------ Output ------ 

For each test case, output a single line containing the integer L: the maximum length of the longest common contiguous subsequence.

------ Constraints ------ 

$1 ≤ T ≤  100 $
$1 ≤ N ≤  2000 $
$1 ≤ A_{i}, B_{i} ≤  N $
$All the elements in both arrays A and B are distinct.$

----- Sample Input 1 ------ 
2

3

1 3 2

2 1 3

8

3 8 4 2 6 1 5 7

5 2 4 3 8 7 6 1
----- Sample Output 1 ------ 
2

4
----- explanation 1 ------ 

First Example :  
One of the possible card arrangements is: 
1 2 3 
2 3 1 

Length of the longest common contiguous subsequence between [1, 2, 3] and [2, 3, 1] is 2, [2, 3]. And that's the maximum possible, so answer is 2.

Second Example:  
One of the possible card arrangements is : 
7 3 2 8 6 5 4 1 
1 5 3 2 8 6 4 7 

The longest common contiguous subsequence has length 4 [3, 2, 8, 6] here. There is no way to arrange these cards such that it's more than 4.

Note
Let L be the answer. Let Ci be the value written on the top of the card at ith position and Di be the value written on the bottom of the card at ith position after rearranging. Then, there should be a pair (x, y) (1 ? x,y ? N-L+1) such that the condition  Cx+j = Dy+j is satisfied for all j, where 0 ? j .

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

String algorithms

Greedy algorithms

Dynamic programming


Solutions:
import sys
import array
upper_bound = 2005
pos = array.array('Q', [0 for _ in range(2010)])
f = [array.array('Q', [0 for _ in range(2010)]) for _ in range(2010)]

def init(stop):
	for i in range(1, stop + 2):
		for j in range(1, i + 1):
			f[i][j] = max(f[i][j], f[i - j][j] + j - 1)
			if i >= j + 1:
				f[i][j] = max(f[i][j], f[i - j - 1][j] + j)
init(upper_bound)
t = int(input())
for _ in range(t):
	n = int(input())
	a = tuple(map(int, sys.stdin.readline().strip().split()))
	for (i, it) in enumerate(a):
		pos[it] = i
	b = tuple(map(int, sys.stdin.readline().strip().split()))
	ct = array.array('Q', [0 for _ in range(n + 1)])
	vis = array.array('Q', [0 for _ in range(n + 1)])
	for i in range(n):
		if vis[i] == 0:
			now = i
			su = 0
			while vis[now] == 0:
				vis[now] = 1
				su += 1
				now = pos[b[now]]
			ct[su] += 1
	answ = ct[1]
	v = [j for j in range(1, n + 1) if ct[j] != 0]
	for i in range(1, n + 1):
		ret = 0
		for j in v:
			ret += ct[j] * f[j][i]
		answ = max(answ, ret)
	print(answ)