We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:

• A[i] == B[j];
• The line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting lines 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

Let’s split this into small sub problems

### Example:

Input: A = [1,4,2], B = [1,2,4] Output: 2 Let’s loop through A and B and consider each element and check how many lines can be drawn

• if A[i] == B[i] then 1 + dp[i-1][j-1] i.e., how many lines are drawn before this
• else, we take the max of prev row(dp[i-1][j]) and column(dp[i][j-1])

Code

``````/**
* @param {number[]} A
* @param {number[]} B
* @return {number}
*/
var maxUncrossedLines = function(A, B) {
let m = A.length, n = B.length

let dp = new Array(m + 1);

for (let i = 0; i <= m; i++) {
dp[i] = new Array(n + 1).fill(0);s
}

for(let i = 1; i <= m; i++) {
for(let j = 1; j <= n; j++) {
if(A[i - 1] == B[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1]
} else {
dp[i][j] = Math.max(dp[i- 1][j], dp[i][j - 1])
}
}
}

return dp[m][n]
};
``````

This post is also available on DEV.