Dada una array arr[] de N enteros, la tarea es encontrar e imprimir la subsecuencia creciente más larga.
Ejemplos:
Entrada: arr[] = {12, 34, 1, 5, 40, 80}
Salida: 4
{12, 34, 40, 80} y {1, 5, 40, 80} son las
subsecuencias crecientes más largas.
Entrada: arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}
Salida: 6
Prerrequisito: LCS , LIS
Enfoque: La subsecuencia creciente más larga de cualquier secuencia es la subsecuencia de la secuencia ordenada de sí misma. Se puede resolver usando un enfoque de Programación Dinámica . El enfoque es el mismo que el del problema LCS clásico , pero en lugar de la segunda secuencia, la secuencia dada se toma nuevamente en su forma ordenada.
Nota: debemos eliminar todos los duplicados; de lo contrario, podría dar un resultado incorrecto. Por ejemplo, en {1, 1, 1} sabemos que la subsecuencia creciente más larga (a1 < a2 < … ak) tiene una longitud de 1, pero si probamos este ejemplo en LIS usando el método LCS obtendríamos 3 (porque encuentra el subsecuencia común más larga).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
//function to return size of array without duplicates
int removeDuplicates(vector<int> &arr)
{
int k = 0;
for (int i = 1; i < arr.size(); i++)
{
if (arr[i] != arr[k]) {
arr[++k] = arr[i];
}
}
return k + 1;
}
// Function to return the size of the
// longest increasing subsequence
int LISusingLCS(vector<int>& seq)
{
int n = seq.size();
// Create an 2D array of integer
// for tabulation
vector<vector<int> > L(n + 1, vector<int>(n + 1));
// Take the second sequence as the sorted
// sequence of the given sequence
vector<int> sortedseq(seq);
sort(sortedseq.begin(), sortedseq.end());
//remove duplicates
int m = removeDuplicates(sortedseq)
// Classical Dynamic Programming algorithm
// for Longest Common Subsequence
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (seq[i - 1] == sortedseq[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
// Return the ans
return L[n][m];
}
// Driver code
int main()
{
vector<int> sequence{ 12, 34, 1, 5, 40, 80 };
cout << LISusingLCS(sequence) << endl;
return 0;
}
Java
//Java implementation of above approach
import java.util.*;
class GFG
{
// Function to return the size of the
// longest increasing subsequence
static int LISusingLCS(Vector<Integer> seq)
{
int n = seq.size();
// Create an 2D array of integer
// for tabulation
int L[][] = new int [n + 1][n + 1];
// Take the second sequence as the sorted
// sequence of the given sequence
Vector<Integer> sortedseq = new Vector<Integer>(seq);
Collections.sort(sortedseq);
// Classical Dynamic Programming algorithm
// for Longest Common Subsequence
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (seq.get(i - 1) == sortedseq.get(j - 1))
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = Math.max(L[i - 1][j],
L[i][j - 1]);
}
}
// Return the ans
return L[n][n];
}
// Driver code
public static void main(String args[])
{
Vector<Integer> sequence = new Vector<Integer>();
sequence.add(12);
sequence.add(34);
sequence.add(1);
sequence.add(5);
sequence.add(40);
sequence.add(80);
System.out.println(LISusingLCS(sequence));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Function to return the size of the # longest increasing subsequence def LISusingLCS(seq): n = len(seq) # Create an 2D array of integer # for tabulation L = [[0 for i in range(n + 1)] for i in range(n + 1)] # Take the second sequence as the sorted # sequence of the given sequence sortedseq = sorted(seq) # Classical Dynamic Programming algorithm # for Longest Common Subsequence for i in range(n + 1): for j in range(n + 1): if (i == 0 or j == 0): L[i][j] = 0 elif (seq[i - 1] == sortedseq[j - 1]): L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1]) # Return the ans return L[n][n] # Driver code sequence = [12, 34, 1, 5, 40, 80] print(LISusingLCS(sequence)) # This code is contributed by mohit kumar
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the size of the
// longest increasing subsequence
static int LISusingLCS(List<int> seq)
{
int n = seq.Count;
// Create an 2D array of integer
// for tabulation
int [,]L = new int [n + 1, n + 1];
// Take the second sequence as the sorted
// sequence of the given sequence
List<int> sortedseq = new List<int>(seq);
sortedseq.Sort();
// Classical Dynamic Programming algorithm
// for longest Common Subsequence
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i, j] = 0;
else if (seq[i - 1] == sortedseq[j - 1])
L[i, j] = L[i - 1, j - 1] + 1;
else
L[i,j] = Math.Max(L[i - 1, j],
L[i, j - 1]);
}
}
// Return the ans
return L[n, n];
}
// Driver code
public static void Main(String []args)
{
List<int> sequence = new List<int>();
sequence.Add(12);
sequence.Add(34);
sequence.Add(1);
sequence.Add(5);
sequence.Add(40);
sequence.Add(80);
Console.WriteLine(LISusingLCS(sequence));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
//Javascript implementation of above approach
// Function to return the size of the
// longest increasing subsequence
function LISusingLCS(seq)
{
let n = seq.length;
// Create an 2D array of integer
// for tabulation
let L = new Array(n + 1);
for(let i = 0; i < (n + 1); i++)
{
L[i] = new Array(n + 1);
for(let j = 0; j < (n + 1); j++)
{
L[i][j] = 0;
}
}
// Take the second sequence as the sorted
// sequence of the given sequence
let sortedseq =[...seq];
sortedseq.sort(function(a,b){return a-b;});
// Classical Dynamic Programming algorithm
// for Longest Common Subsequence
for (let i = 0; i <= n; i++)
{
for (let j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (seq[i - 1] == sortedseq[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = Math.max(L[i - 1][j],
L[i][j - 1]);
}
}
// Return the ans
return L[n][n];
}
// Driver code
let sequence = [12, 34, 1, 5, 40, 80];
document.write(LISusingLCS(sequence));
// This code is contributed by patel2127
</script>
4
Complejidad de Tiempo: O(n 2 ) donde n es la longitud de la secuencia
Espacio Auxiliar: O(n 2 )
Publicación traducida automáticamente
Artículo escrito por Aakash_Panchal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA