Longest Common Subsequence

You are given two arrays of integers. Your task is to find the length of the longest common subsequence (LCS) between these two arrays.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For arrays A and B, the LCS is the longest sequence that appears in both A and B.

The recurrence relation for the dynamic programming solution is given by:

\( dp[i+1][j+1] = \begin{cases} dp[i][j] + 1, & \text{if } A[i] = B[j] \\ \max(dp[i+1][j], dp[i][j+1]), & \text{otherwise} \end{cases} \)

inputFormat

The input consists of two lines. The first line contains the elements of the first integer array separated by spaces, and the second line contains the elements of the second integer array separated by spaces.

outputFormat

Output a single integer which is the length of the longest common subsequence of the two arrays.

3 4 9 1
5 3 8 9 10 2 1

3