Dados dos arreglos arr1[] y arr2[] , la tarea es encontrar el subarreglo más largo de arr1 [] que es una subsecuencia de arr2[] .
Ejemplos:
Entrada: arr1[] = {4, 2, 3, 1, 5, 6}, arr2[] = {3, 1, 4, 6, 5, 2}
Salida: 3
Explicación: El subarreglo más largo de arr1[] que es una subsecuencia en arr2[] es {3, 1, 5}Entrada: arr1[] = {3, 2, 4, 7, 1, 5, 6, 8, 10, 9}, arr2[] = {9, 2, 4, 3, 1, 5, 6, 8, 10 , 7}
Salida: 5
Explicación: El subarreglo más largo en arr1[] que es una subsecuencia en arr2[] es {1, 5, 6, 8, 10}.
Enfoque: La idea es utilizar Programación Dinámica para resolver este problema. Siga los pasos a continuación para resolver el problema:
- Inicialice una tabla DP[][] , donde DP[i][j] almacena la longitud del subarreglo más largo hasta el i -ésimo índice en arr1[] que es una subsecuencia en arr2[] hasta el j -ésimo índice.
- Ahora, recorra ambas arrays y realice lo siguiente:
- Caso 1: si arr1[i] y arr2[j] son iguales, agregue 1 a DP[i – 1][j – 1] ya que arr1[i] y arr2[j] contribuyen a la longitud requerida del subarreglo más largo.
- Caso 2: si arr1[i] y arr2[j] no son iguales, establezca DP[i][j] = DP[i – 1][j] .
- Finalmente, imprima el valor máximo presente en la tabla DP[][] como la respuesta requerida.
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 find the length of the
// longest subarray in arr1[] which
// is a subsequence in arr2[]
int LongSubarrSeq(int arr1[], int arr2[], int M, int N)
{
// Length of the array arr1[]
// Length of the required
// longest subarray
int maxL = 0;
// Initialize DP[]array
int DP[M + 1][N + 1];
// Traverse array arr1[]
for (int i = 1; i <= M; i++)
{
// Traverse array arr2[]
for (int j = 1; j <= N; j++)
{
if (arr1[i - 1] == arr2[j - 1])
{
// arr1[i - 1] contributes to
// the length of the subarray
DP[i][j] = 1 + DP[i - 1][j - 1];
}
// Otherwise
else
{
DP[i][j] = DP[i][j - 1];
}
}
}
// Find the maximum value
// present in DP[][]
for (int i = 1; i <= M; i++)
{
for (int j = 1; j <= N; j++)
{
maxL = max(maxL, DP[i][j]);
}
}
// Return the result
return maxL;
}
// Driver Code
int main()
{
int arr1[] = { 4, 2, 3, 1, 5, 6 };
int M = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = { 3, 1, 4, 6, 5, 2 };
int N = sizeof(arr2) / sizeof(arr2[0]);
// Function call to find the length
// of the longest required subarray
cout << LongSubarrSeq(arr1, arr2, M, N) <<endl;
return 0;
}
// This code is contributed by code_hunt.
Java
// Java program
// for the above approach
import java.io.*;
class GFG {
// Function to find the length of the
// longest subarray in arr1[] which
// is a subsequence in arr2[]
private static int LongSubarrSeq(
int[] arr1, int[] arr2)
{
// Length of the array arr1[]
int M = arr1.length;
// Length of the array arr2[]
int N = arr2.length;
// Length of the required
// longest subarray
int maxL = 0;
// Initialize DP[]array
int[][] DP = new int[M + 1][N + 1];
// Traverse array arr1[]
for (int i = 1; i <= M; i++) {
// Traverse array arr2[]
for (int j = 1; j <= N; j++) {
if (arr1[i - 1] == arr2[j - 1]) {
// arr1[i - 1] contributes to
// the length of the subarray
DP[i][j] = 1 + DP[i - 1][j - 1];
}
// Otherwise
else {
DP[i][j] = DP[i][j - 1];
}
}
}
// Find the maximum value
// present in DP[][]
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++) {
maxL = Math.max(maxL, DP[i][j]);
}
}
// Return the result
return maxL;
}
// Driver Code
public static void main(String[] args)
{
int[] arr1 = { 4, 2, 3, 1, 5, 6 };
int[] arr2 = { 3, 1, 4, 6, 5, 2 };
// Function call to find the length
// of the longest required subarray
System.out.println(LongSubarrSeq(arr1, arr2));
}
}
Python3
# Python program # for the above approach # Function to find the length of the # longest subarray in arr1 which # is a subsequence in arr2 def LongSubarrSeq(arr1, arr2): # Length of the array arr1 M = len(arr1); # Length of the array arr2 N = len(arr2); # Length of the required # longest subarray maxL = 0; # Initialize DParray DP = [[0 for i in range(N + 1)] for j in range(M + 1)]; # Traverse array arr1 for i in range(1, M + 1): # Traverse array arr2 for j in range(1, N + 1): if (arr1[i - 1] == arr2[j - 1]): # arr1[i - 1] contributes to # the length of the subarray DP[i][j] = 1 + DP[i - 1][j - 1]; # Otherwise else: DP[i][j] = DP[i][j - 1]; # Find the maximum value # present in DP for i in range(M + 1): # Traverse array arr2 for j in range(1, N + 1): maxL = max(maxL, DP[i][j]); # Return the result return maxL; # Driver Code if __name__ == '__main__': arr1 = [4, 2, 3, 1, 5, 6]; arr2 = [3, 1, 4, 6, 5, 2]; # Function call to find the length # of the longest required subarray print(LongSubarrSeq(arr1, arr2)); # This code contributed by shikhasingrajput
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the length of the
// longest subarray in arr1[] which
// is a subsequence in arr2[]
private static int LongSubarrSeq(int[] arr1,
int[] arr2)
{
// Length of the array arr1[]
int M = arr1.Length;
// Length of the array arr2[]
int N = arr2.Length;
// Length of the required
// longest subarray
int maxL = 0;
// Initialize DP[]array
int[,] DP = new int[M + 1, N + 1];
// Traverse array arr1[]
for(int i = 1; i <= M; i++)
{
// Traverse array arr2[]
for(int j = 1; j <= N; j++)
{
if (arr1[i - 1] == arr2[j - 1])
{
// arr1[i - 1] contributes to
// the length of the subarray
DP[i, j] = 1 + DP[i - 1, j - 1];
}
// Otherwise
else
{
DP[i, j] = DP[i, j - 1];
}
}
}
// Find the maximum value
// present in DP[][]
for(int i = 1; i <= M; i++)
{
for(int j = 1; j <= N; j++)
{
maxL = Math.Max(maxL, DP[i, j]);
}
}
// Return the result
return maxL;
}
// Driver Code
static public void Main()
{
int[] arr1 = { 4, 2, 3, 1, 5, 6 };
int[] arr2 = { 3, 1, 4, 6, 5, 2 };
// Function call to find the length
// of the longest required subarray
Console.WriteLine(LongSubarrSeq(arr1, arr2));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// javascript program of the above approach
// Function to find the length of the
// longest subarray in arr1[] which
// is a subsequence in arr2[]
function LongSubarrSeq(
arr1, arr2)
{
// Length of the array arr1[]
let M = arr1.length;
// Length of the array arr2[]
let N = arr2.length;
// Length of the required
// longest subarray
let maxL = 0;
// Initialize DP[]array
let DP = new Array(M + 1);
// Loop to create 2D array using 1D array
for (var i = 0; i < DP.length; i++) {
DP[i] = new Array(2);
}
for (var i = 0; i < DP.length; i++) {
for (var j = 0; j < DP.length; j++) {
DP[i][j] = 0;
}
}
// Traverse array arr1[]
for (let i = 1; i <= M; i++) {
// Traverse array arr2[]
for (let j = 1; j <= N; j++) {
if (arr1[i - 1] == arr2[j - 1]) {
// arr1[i - 1] contributes to
// the length of the subarray
DP[i][j] = 1 + DP[i - 1][j - 1];
}
// Otherwise
else {
DP[i][j] = DP[i][j - 1];
}
}
}
// Find the maximum value
// present in DP[][]
for (let i = 1; i <= M; i++) {
for (let j = 1; j <= N; j++) {
maxL = Math.max(maxL, DP[i][j]);
}
}
// Return the result
return maxL;
}
// Driver Code
let arr1 = [ 4, 2, 3, 1, 5, 6 ];
let arr2 = [ 3, 1, 4, 6, 5, 2 ];
// Function call to find the length
// of the longest required subarray
document.write(LongSubarrSeq(arr1, arr2));
</script>
Producción:
3
Complejidad de Tiempo: O(M * N)
Espacio Auxiliar: O(M * N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array