Uncrossed Lines

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 line 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.

Example 1:

Input: A = [1,4,2], B = [1,2,4]
Output: 2

Approach

Java

public class UncrossedLines {
    public static void main(String[] args) {
        int[] A = { 1, 4, 2 };
        int[] B = { 1, 2, 4 };
        System.out.println(maxUncrossedLines(A, B));
    }

    static int maxUncrossedLines(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int dp[][] = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {

                // if any array is empty then
                // dp[i][j]=0
                if (i == 0 || j == 0)
                    dp[i][j] = 0;

                // if both are same then update result
                // 1 more than the previous
                else if (A[i - 1] == B[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];

                // else max of both values
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int maxUncrossedLines(vector<int> &A, vector<int> &B)
{
    int n = A.size(), m = B.size();
    int dp[n + 1][m + 1];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {

            //if any array is empty then
            //dp[i][j]=0
            if (i == 0 || j == 0)
                dp[i][j] = 0;

            //if both are same then update result
            //1 more than the previous
            else if (A[i - 1] == B[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];

            //else max of both values
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

int main()
{
    vector<int> A = {1, 4, 2};
    vector<int> B = {1, 2, 4};
    cout << maxUncrossedLines(A, B);
    return 0;
}