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++
// 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
// 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
# 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#
// 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
}
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA