Uncrossed Lines
You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2, in the order they are given, on two separate horizontal lines.
We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:
nums1[i] == nums2[j].- The line we draw does not intersect any other connecting non-horizontal line.
Note that a connecting line cannot intersect even at the endpoints; each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
Example 1
Input
nums1 = [1,4,2], nums2 = [1,2,4]Output
2We can draw 2 uncrossed lines, but drawing all 3 would cause the line from nums1[1] = 4 to nums2[2] = 4 to intersect the line from nums1[2] = 2 to nums2[1] = 2.
Example 2
Input
nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]Output
3The maximum number of non-intersecting connections between equal values is 3.
Constraints
- 1 <= nums1.length, nums2.length <= 500
- 1 <= nums1[i], nums2[j] <= 2000