Dadas dos arrays, encuentre la longitud de la subsecuencia creciente común más larga [LCIS] e imprima una de esas secuencias (pueden existir múltiples secuencias)
Supongamos que consideramos dos arrays:
arr1[] = {3, 4, 9, 1} y
arr2[] = {5, 3, 8, 9, 10, 2, 1}
Nuestra respuesta sería {3, 9} ya que esta es la subsecuencia común más larga que también es creciente.
La idea es usar programación dinámica aquí también. Almacenamos la subsecuencia creciente común más larga que termina en cada índice de arr2[]. Creamos una tabla de array auxiliar [] tal que la tabla [j] almacena la longitud de LCIS que termina con arr2 [j]. Al final, devolvemos el valor máximo de esta tabla. Para llenar los valores en esta tabla, recorremos todos los elementos de arr1[] y para cada elemento arr1[i], recorremos todos los elementos de arr2[]. Si encontramos una coincidencia, actualizamos la tabla [j] con la longitud del LCIS actual. Para mantener el LCIS actual, seguimos comprobando los valores válidos de la tabla [j].
A continuación se muestra el programa para encontrar la longitud de LCIS.
C++
// A C++ Program to find length of the Longest Common
// Increasing Subsequence (LCIS)
#include<bits/stdc++.h>
using namespace std;
// Returns the length and the LCIS of two
// arrays arr1[0..n-1] and arr2[0..m-1]
int LCIS(int arr1[], int n, int arr2[], int m)
{
// table[j] is going to store length of LCIS
// ending with arr2[j]. We initialize it as 0,
int table[m];
for (int j=0; j<m; j++)
table[j] = 0;
// Traverse all elements of arr1[]
for (int i=0; i<n; i++)
{
// Initialize current length of LCIS
int current = 0;
// For each element of arr1[], traverse all
// elements of arr2[].
for (int j=0; j<m; j++)
{
// If both the array have same elements.
// Note that we don't break the loop here.
if (arr1[i] == arr2[j])
if (current + 1 > table[j])
table[j] = current + 1;
/* Now seek for previous smaller common
element for current element of arr1 */
if (arr1[i] > arr2[j])
if (table[j] > current)
current = table[j];
}
}
// The maximum value in table[] is out result
int result = 0;
for (int i=0; i<m; i++)
if (table[i] > result)
result = table[i];
return result;
}
/* Driver program to test above function */
int main()
{
int arr1[] = {3, 4, 9, 1};
int arr2[] = {5, 3, 8, 9, 10, 2, 1};
int n = sizeof(arr1)/sizeof(arr1[0]);
int m = sizeof(arr2)/sizeof(arr2[0]);
cout << "Length of LCIS is "
<< LCIS(arr1, n, arr2, m);
return (0);
}
Java
// A Java Program to find length of the Longest
// Common Increasing Subsequence (LCIS)
import java.io.*;
class GFG {
// Returns the length and the LCIS of two
// arrays arr1[0..n-1] and arr2[0..m-1]
static int LCIS(int arr1[], int n, int arr2[],
int m)
{
// table[j] is going to store length of
// LCIS ending with arr2[j]. We initialize
// it as 0,
int table[] = new int[m];
for (int j = 0; j < m; j++)
table[j] = 0;
// Traverse all elements of arr1[]
for (int i = 0; i < n; i++)
{
// Initialize current length of LCIS
int current = 0;
// For each element of arr1[], traverse
// all elements of arr2[].
for (int j = 0; j < m; j++)
{
// If both the array have same
// elements. Note that we don't
// break the loop here.
if (arr1[i] == arr2[j])
if (current + 1 > table[j])
table[j] = current + 1;
/* Now seek for previous smaller
common element for current
element of arr1 */
if (arr1[i] > arr2[j])
if (table[j] > current)
current = table[j];
}
}
// The maximum value in table[] is out
// result
int result = 0;
for (int i=0; i<m; i++)
if (table[i] > result)
result = table[i];
return result;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr1[] = {3, 4, 9, 1};
int arr2[] = {5, 3, 8, 9, 10, 2, 1};
int n = arr1.length;
int m = arr2.length;
System.out.println("Length of LCIS is " +
LCIS(arr1, n, arr2, m));
}
}
// This code is contributed by Prerna Saini
Python 3
# Python 3 Program to find length of the
# Longest Common Increasing Subsequence (LCIS)
# Returns the length and the LCIS of two
# arrays arr1[0..n-1] and arr2[0..m-1]
def LCIS(arr1, n, arr2, m):
# table[j] is going to store length of LCIS
# ending with arr2[j]. We initialize it as 0,
table = [0] * m
for j in range(m):
table[j] = 0
# Traverse all elements of arr1[]
for i in range(n):
# Initialize current length of LCIS
current = 0
# For each element of arr1[],
# traverse all elements of arr2[].
for j in range(m):
# If both the array have same elements.
# Note that we don't break the loop here.
if (arr1[i] == arr2[j]):
if (current + 1 > table[j]):
table[j] = current + 1
# Now seek for previous smaller common
# element for current element of arr1
if (arr1[i] > arr2[j]):
if (table[j] > current):
current = table[j]
# The maximum value in table[]
# is out result
result = 0
for i in range(m):
if (table[i] > result):
result = table[i]
return result
# Driver Code
if __name__ == "__main__":
arr1 = [3, 4, 9, 1]
arr2 = [5, 3, 8, 9, 10, 2, 1]
n = len(arr1)
m = len(arr2)
print("Length of LCIS is",
LCIS(arr1, n, arr2, m))
# This code is contributed by ita_c
C#
// A C# Program to find length of the Longest
// Common Increasing Subsequence (LCIS)
using System;
class GFG {
// Returns the length and the LCIS of two
// arrays arr1[0..n-1] and arr2[0..m-1]
static int LCIS(int []arr1, int n,
int []arr2, int m)
{
// table[j] is going to store length of
// LCIS ending with arr2[j]. We initialize
// it as 0,
int []table = new int[m];
for (int j = 0; j < m; j++)
table[j] = 0;
// Traverse all elements of arr1[]
for (int i = 0; i < n; i++)
{
// Initialize current length of LCIS
int current = 0;
// For each element of arr1[], traverse
// all elements of arr2[].
for (int j = 0; j < m; j++)
{
// If both the array have same
// elements. Note that we don't
// break the loop here.
if (arr1[i] == arr2[j])
if (current + 1 > table[j])
table[j] = current + 1;
/* Now seek for previous smaller
common element for current
element of arr1 */
if (arr1[i] > arr2[j])
if (table[j] > current)
current = table[j];
}
}
// The maximum value in
// table[] is out result
int result = 0;
for (int i = 0; i < m; i++)
if (table[i] > result)
result = table[i];
return result;
}
/* Driver program to test above function */
public static void Main()
{
int []arr1 = {3, 4, 9, 1};
int []arr2 = {5, 3, 8, 9, 10, 2, 1};
int n = arr1.Length;
int m = arr2.Length;
Console.Write("Length of LCIS is " +
LCIS(arr1, n, arr2, m));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program to find length of
// the Longest Common Increasing
// Subsequence (LCIS)
// Returns the length and the LCIS
// of two arrays arr1[0..n-1] and
// arr2[0..m-1]
function LCIS($arr1, $n, $arr2, $m)
{
// table[j] is going to store
// length of LCIS ending with
// arr2[j]. We initialize it as 0,
$table = Array();
//int table[m];
for ($j = 0; $j < $m; $j++)
$table[$j] = 0;
// Traverse all elements of arr1[]
for ($i = 0; $i < $n; $i++)
{
// Initialize current
// length of LCIS
$current = 0;
// For each element of
// arr1[], traverse all
// elements of arr2[].
for ($j = 0; $j < $m; $j++)
{
// If both the array have
// same elements. Note that
// we don't break the loop here.
if ($arr1[$i] == $arr2[$j])
if ($current + 1 > $table[$j])
$table[$j] = $current + 1;
/* Now seek for previous smaller
common element for current
element of arr1 */
if ($arr1[$i] > $arr2[$j])
if ($table[$j] > $current)
$current = $table[$j];
}
}
// The maximum value in
// table[] is out result
$result = 0;
for ($i = 0; $i < $m; $i++)
if ($table[$i] > $result)
$result = $table[$i];
return $result;
}
// Driver Code
$arr1 = array (3, 4, 9, 1);
$arr2 = array (5, 3, 8, 9, 10, 2, 1);
$n = sizeof($arr1);
$m = sizeof($arr2);
echo "Length of LCIS is ",
LCIS($arr1, $n, $arr2, $m);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript Program to find length of the Longest
// Common Increasing Subsequence (LCIS)
// Returns the length and the LCIS of two
// arrays arr1[0..n-1] and arr2[0..m-1]
function LCIS(arr1, n, arr2, m)
{
// table[j] is going to store length of
// LCIS ending with arr2[j]. We initialize
// it as 0,
let table = [];
for (let j = 0; j < m; j++)
table[j] = 0;
// Traverse all elements of arr1[]
for (let i = 0; i < n; i++)
{
// Initialize current length of LCIS
let current = 0;
// For each element of arr1[], traverse
// all elements of arr2[].
for (let j = 0; j < m; j++)
{
// If both the array have same
// elements. Note that we don't
// break the loop here.
if (arr1[i] == arr2[j])
if (current + 1 > table[j])
table[j] = current + 1;
/* Now seek for previous smaller
common element for current
element of arr1 */
if (arr1[i] > arr2[j])
if (table[j] > current)
current = table[j];
}
}
// The maximum value in table[] is out
// result
let result = 0;
for (let i=0; i<m; i++)
if (table[i] > result)
result = table[i];
return result;
}
// Driver Code
let arr1 = [3, 4, 9, 1];
let arr2 = [5, 3, 8, 9, 10, 2, 1];
let n = arr1.length;
let m = arr2.length;
document.write("Length of LCIS is " +
LCIS(arr1, n, arr2, m));
</script>
Producción :
Length of LCIS is 2
Complejidad de tiempo: O(n*m) , donde n y m representan el tamaño de las dos arrays dadas.
Espacio auxiliar: O(m), donde m representa el tamaño de la segunda array dada.
Este artículo es aportado por Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA