解题思路

这道题与经典的“非交叉连线”/“最长公共子序列（LCS）”完全等价：

• 若把 nums1[i] 与 nums2[j] 连线，要求所有连线不相交，就意味着这些配对的下标必须保持共同递增顺序（即若 (i1, j1)、(i2, j2) 都被选中且 i1 < i2，必须有 j1 < j2）。
• 这正是最长公共子序列的定义：从两个序列中找一个顺序一致的最长相同子序列。 因此，答案就是 LCS(nums1, nums2) 的长度。

算法：动态规划（LCS）

题目内容

在两条独立的水平线上按给定的顺序写下 $nums1$ 和 $nums2$ 中的整数。

现在，可以绘制一些连接两个数字 $nums1[i]$ 和 $nums2[j]$ 的直线，这些直线需要同时满足满足： $nums1[i]==nums2[j]$

且绘制的直线不与任何其他连线(非水平线)相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

$1 <=nums1.length,nums2.length<=2000$

$1 <= nums1[i]，nums2[i]<= 2000$

输入描述

每组输入为两行，表示 $nums1$ 和 $nums2$ 两个数组。每行有 $n+1$ 个数字，数字间用空格分开，第一个数字表示数组个数 $n$ ，后面跟 $n$ 个数字；如 $2$ $23$，表示数组有 $2$ 个元素，元素值为 $2$ 和 $3$

输出描述

输出最多能绘制不想交线的条数。

样例1

输入

3 1 4 2
3 1 2 4

输出

2

样例2

输入

5 1 2 2 3 4
5 2 2 2 4 1

输出

3