Longest common subsequence - MarisaOJ: Marisa Online Judge

You are given 2 arrays

$A, B$ both of

$n$ integers, find the longest common subsequence (LCS) of

$A$ and

$B$ . In other words, find the largest

$k$ that there exist some indices

$i_1 < i_2 < ... < i_k$ and

$j_1 < j_2 < ... < j_k$ that:

$A_{i_1} = B_{j_1}$

$A_{i_2} = B_{j_2}$

$...$

$A_{i_k} = B_{j_k}$ ### Input - The first line contains an integer

$n$ . - The second line contains

$n$ integers

$A_i$ . - The third line contains

$n$ integers

$B_i$ . ### Output - Print the length of the LCS. ### Constraints -

$1 \le n \le 1000$ -

$1 \le A_i, B_i \le 10^9$ . ### Example Input:

$4 1 2 3 4 3 4 2 1$

Output:

$2$

Note: The LCS is

$(3, 4)$ .

Introduction to dynamic programming
	Hakurei Shrine
	Buying tickets
	Reading 2
	Longest increasing subsequence
	Jealousy
	Maximum path 2
	Fences painting
	Hall
	Knapsack 2
	Longest common subsequence
	Yet another build array problem
	Rectangle cutting
	Palindrome query
	Marisa
	Merging elements
	Brewing potion 8

Topic

Dynamic Programming

Rating

1100

Solution (1)

Solution