Número máximo de líneas no cruzadas entre dos arrays dadas

Dadas dos arrays A[] y B[] , la tarea es encontrar el número máximo de líneas sin cruzar entre los elementos de las dos arrays dadas.

Se puede dibujar una línea recta entre dos elementos de array A[i] y B[j] solo si:

• A[i] = B[j]
• La línea no se cruza con ninguna otra línea.

Ejemplos:

Entrada: A[] = {3, 9, 2}, B[] = {3, 2, 9} 
Salida: 2 
Explicación: 
Las líneas entre A[0] a B[0] y A[1] a B[ 2] no se cruzan entre sí.

Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {1, 2, 3, 4, 5} 
Salida: 5

Enfoque ingenuo: la idea es generar todas las subsecuencias del arreglo A[] e intentar encontrarlas en el arreglo B[] para que las dos subsecuencias puedan conectarse uniendo líneas rectas. La subsecuencia más larga que se encuentre común en A[] y B[] tendría el número máximo de líneas sin cruzar. Así que imprime la longitud de esa subsecuencia.

Complejidad de Tiempo: O(M * 2 ^N ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: del enfoque anterior, se puede observar que la tarea es encontrar la subsecuencia más larga común en ambas arrays. Por lo tanto, el enfoque anterior se puede optimizar encontrando la subsecuencia común más larga entre las dos arrays mediante la programación dinámica .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count maximum number
// of uncrossed lines between the
// two given arrays
int uncrossedLines(int* a, int* b,
                   int n, int m)
{
    // Stores the length of lcs
    // obtained upto every index
    int dp[n + 1][m + 1];
 
    // Iterate over first array
    for (int i = 0; i <= n; i++) {
 
        // Iterate over second array
        for (int j = 0; j <= m; j++) {
 
            if (i == 0 || j == 0)
 
                // Update value in dp table
                dp[i][j] = 0;
 
            // If both characters
            // are equal
            else if (a[i - 1] == b[j - 1])
 
                // Update the length of lcs
                dp[i][j] = 1 + dp[i - 1][j - 1];
 
            // If both characters
            // are not equal
            else
 
                // Update the table
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j - 1]);
        }
    }
 
    // Return the answer
    return dp[n][m];
}
 
// Driver Code
int main()
{
    // Given array A[] and B[]
    int A[] = { 3, 9, 2 };
    int B[] = { 3, 2, 9 };
 
    int N = sizeof(A) / sizeof(A[0]);
    int M = sizeof(B) / sizeof(B[0]);
 
    // Function Call
    cout << uncrossedLines(A, B, N, M);
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to count maximum number
// of uncrossed lines between the
// two given arrays
static int uncrossedLines(int[] a, int[] b,
                          int n, int m)
{
     
    // Stores the length of lcs
    // obtained upto every index
    int[][] dp = new int[n + 1][m + 1];
 
    // Iterate over first array
    for(int i = 0; i <= n; i++)
    {
         
        // Iterate over second array
        for(int j = 0; j <= m; j++)
        {
            if (i == 0 || j == 0)
             
                // Update value in dp table
                dp[i][j] = 0;
 
            // If both characters
            // are equal
            else if (a[i - 1] == b[j - 1])
 
                // Update the length of lcs
                dp[i][j] = 1 + dp[i - 1][j - 1];
 
            // If both characters
            // are not equal
            else
 
                // Update the table
                dp[i][j] = Math.max(dp[i - 1][j],
                                    dp[i][j - 1]);
        }
    }
 
    // Return the answer
    return dp[n][m];
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given array A[] and B[]
    int A[] = { 3, 9, 2 };
    int B[] = { 3, 2, 9 };
 
    int N = A.length;
    int M = B.length;
 
    // Function call
    System.out.print(uncrossedLines(A, B, N, M));
}
}
 
// This code is contributed by code_hunt

# Python3 program for
# the above approach
 
# Function to count maximum number
# of uncrossed lines between the
# two given arrays
def uncrossedLines(a, b,
                   n, m):
 
    # Stores the length of lcs
    # obtained upto every index
    dp = [[0 for x in range(m + 1)]
             for y in range(n + 1)]
  
    # Iterate over first array
    for i in range (n + 1):
  
        # Iterate over second array
        for j in range (m + 1):
  
            if (i == 0 or j == 0):
  
                # Update value in dp table
                dp[i][j] = 0
  
            # If both characters
            # are equal
            elif (a[i - 1] == b[j - 1]):
  
                # Update the length of lcs
                dp[i][j] = 1 + dp[i - 1][j - 1]
  
            # If both characters
            # are not equal
            else:
  
                # Update the table
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j - 1])
  
    # Return the answer
    return dp[n][m]
  
# Driver Code
if __name__ == "__main__":
   
    # Given array A[] and B[]
    A = [3, 9, 2]
    B = [3, 2, 9]
  
    N = len(A)
    M = len(B)
  
    # Function Call
    print (uncrossedLines(A, B, N, M))
 
# This code is contributed by Chitranayal

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count maximum number
// of uncrossed lines between the
// two given arrays
static int uncrossedLines(int[] a, int[] b,
                          int n, int m)
{
     
    // Stores the length of lcs
    // obtained upto every index
    int[,] dp = new int[n + 1, m + 1];
 
    // Iterate over first array
    for(int i = 0; i <= n; i++)
    {
 
        // Iterate over second array
        for(int j = 0; j <= m; j++)
        {
            if (i == 0 || j == 0)
 
                // Update value in dp table
                dp[i, j] = 0;
 
            // If both characters
            // are equal
            else if (a[i - 1] == b[j - 1])
 
                // Update the length of lcs
                dp[i, j] = 1 + dp[i - 1, j - 1];
 
            // If both characters
            // are not equal
            else
 
                // Update the table
                dp[i, j] = Math.Max(dp[i - 1, j],
                                    dp[i, j - 1]);
        }
    }
 
    // Return the answer
    return dp[n, m];
}
 
// Driver Code
public static void Main (String[] args)
{
     
    // Given array A[] and B[]
    int[] A = { 3, 9, 2 };
    int[] B = { 3, 2, 9 };
 
    int N = A.Length;
    int M = B.Length;
 
    // Function call
    Console.Write(uncrossedLines(A, B, N, M));
}
}
 
// This code is contributed by code_hunt
}

<script>
 
// Javascript program for the above approach
 
// Function to count maximum number
// of uncrossed lines between the
// two given arrays
function uncrossedLines(a, b, n, m)
{
     
    // Stores the length of lcs
    // obtained upto every index
    let dp = new Array(n + 1);
    for(let i = 0; i< (n + 1); i++)
    {
        dp[i] = new Array(m + 1);
        for(let j = 0; j < (m + 1); j++)
        {
            dp[i][j] = 0;
        }
    }
   
    // Iterate over first array
    for(let i = 0; i <= n; i++)
    {
         
        // Iterate over second array
        for(let j = 0; j <= m; j++)
        {
            if (i == 0 || j == 0)
             
                // Update value in dp table
                dp[i][j] = 0;
   
            // If both characters
            // are equal
            else if (a[i - 1] == b[j - 1])
   
                // Update the length of lcs
                dp[i][j] = 1 + dp[i - 1][j - 1];
   
            // If both characters
            // are not equal
            else
   
                // Update the table
                dp[i][j] = Math.max(dp[i - 1][j],
                                    dp[i][j - 1]);
        }
    }
   
    // Return the answer
    return dp[n][m];
}
 
// Driver Code
 
// Given array A[] and B[]
let A = [ 3, 9, 2 ];
let B = [3, 2, 9];
let N = A.length;
let M = B.length;
 
// Function call
document.write(uncrossedLines(A, B, N, M));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

2

Complejidad temporal: O(N*M) 
Espacio auxiliar: O(N*M)