hardDynamic Programming 2DPure DSA~30 min
Maximum Non-Crossing Matches Between Two Sequences
Two ordered lists of identifiers are placed in parallel rows. Draw connecting lines between equal identifiers so that no two lines cross. Maximize the number of lines drawn.
Problem
Given two integer arrays nums1 and nums2, draw lines connecting equal values nums1[i] == nums2[j] such that the lines do not intersect (connections must preserve order). Return the maximum number of such non-crossing connecting lines.
Input
Two integer arrays nums1 and nums2.
Output
An integer: the maximum number of uncrossed lines.
Constraints
- 1 <= nums1.length, nums2.length <= 500
- 1 <= values <= 2000
- Values may repeat.
Examples
Example 1
Input
nums1 = [1,4,2], nums2 = [1,2,4]
Output
2
Connect the two 1s and the two 4s without crossing (the 2s would cross).
Example 2
Input
nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output
3
Three non-crossing matches are possible.