If you observe carefully, the question asks us to find the longest common subsequence of the two vectors. Let’s consider the example below.
A = [1,4,2]
B = [1,2,4]
There can be two longest common subsequence of A and B, let's consider both:
1. 1,4
2. 1,2
If you select either of them, it is evident that you can connect A & B without crossing the lines.
By the very intrinsic nature of longest common subsequence, the connecting lines cannot cross. Logically speaking, assume A[i] and A[j] (i < j) to be a part of the longest common subsequence (LCS) and B[k] and B[l] (k < l) to be a part of the LCS. Clearly, since i < j and k < l, A[i] has to be equal to B[k] and A[j] has to be equal to B[l]. Thus the lines will not be crossing.
Finding the longest common subsequence of two strings is a standard dynamic programming question. If you are not aware of the solution, consider reading my solution of the problem LC 1143. Longest Common Subsequence.
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
int m = A.size(), n = B.size(), dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i][j - 1], dp[i - 1][j]);
return dp[m][n];
}
Time complexity: O(n^2) Space complexity: O(n^2)