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]
};
```

## Top comments (0)