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)