Longest Common Subsequence (LCS) Length

You are given two sequences of integers. Your task is to compute the length of their Longest Common Subsequence (LCS).

A subsequence of a sequence is obtained by deleting zero or more elements without changing the order of the remaining elements. Formally, if the two sequences are \(P = [p_1, p_2, \dots, p_N]\) and \(Q = [q_1, q_2, \dots, q_M]\), you need to find the maximum integer \(L\) such that there exists indices \(1 \le i_1 < i_2 < \dots < i_L \le N\) and \(1 \le j_1 < j_2 < \dots < j_L \le M\) where \(p_{i_k} = q_{j_k}\) for all \(k = 1, 2, \dots, L\).

Use dynamic programming to achieve an efficient solution.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space, representing the lengths of the two sequences, respectively.

If \(N > 0\), the second line contains \(N\) space-separated integers denoting the first sequence \(P\).
If \(M > 0\), the third line contains \(M\) space-separated integers denoting the second sequence \(Q\).
For cases where \(N = 0\) or \(M = 0\), the corresponding sequence line will be empty.

outputFormat

Output a single integer: the length of the longest common subsequence between the two sequences.

4 5
1 3 4 1
1 2 3 4 1

4