El problema de la subsecuencia creciente más larga (LIS) es encontrar la longitud de la subsecuencia más larga de una secuencia dada de modo que todos los elementos de la subsecuencia se clasifiquen en orden creciente. Por ejemplo, la longitud de LIS para {10, 22, 9, 33, 21, 50, 41, 60, 80} es 6 y LIS es {10, 22, 33, 50, 60, 80}.
Ejemplos:
Input : arr[] = {3, 10, 2, 1, 20}
Output : Length of LIS = 3
The longest increasing subsequence is 3, 10, 20
Input : arr[] = {3, 2}
Output : Length of LIS = 1
The longest increasing subsequences are {3} and {2}
Input : arr[] = {50, 3, 10, 7, 40, 80}
Output : Length of LIS = 4
The longest increasing subsequence is {3, 7, 40, 80}
Subproblemas superpuestos:
considerando la implementación anterior, el siguiente es un árbol de recursión para una array de tamaño 4. lis(n) nos da la longitud de LIS para arr[].
lis(4)
/ |
lis(3) lis(2) lis(1)
/ /
lis(2) lis(1) lis(1)
/
lis(1)
Podemos ver que hay muchos subproblemas que se resuelven una y otra vez. Por lo tanto, este problema tiene la propiedad de subestructura superpuesta y el recálculo de los mismos subproblemas se puede evitar mediante Memoización o Tabulación. A continuación se muestra una implementación tabulada para el problema LIS.
C++
/* Dynamic Programming C/C++ implementation of LIS problem */
#include <iostream>
using namespace std;
/* lis() returns the length of the longest increasing
subsequence in arr[] of size n */
int lis(int arr[], int n)
{
int *lis, i, j, max = 0;
lis = (int*)malloc(sizeof(int) * n);
/* Initialize LIS values for all indexes */
for (i = 0; i < n; i++)
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* Pick maximum of all LIS values */
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
/* Free memory to avoid memory leak */
free(lis);
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
cout <<"Length of lis is "<< lis(arr, n);
return 0;
}
// this code is contributed by shivanisinghss2110
C
/* Dynamic Programming C/C++ implementation of LIS problem */
#include <stdio.h>
#include <stdlib.h>
/* lis() returns the length of the longest increasing
subsequence in arr[] of size n */
int lis(int arr[], int n)
{
int *lis, i, j, max = 0;
lis = (int*)malloc(sizeof(int) * n);
/* Initialize LIS values for all indexes */
for (i = 0; i < n; i++)
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* Pick maximum of all LIS values */
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
/* Free memory to avoid memory leak */
free(lis);
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Length of lis is %d\n", lis(arr, n));
return 0;
}
Java
/* Dynamic Programming Java implementation
of LIS problem */
import java.util.*;
class GFG
{
/*
* lis() returns the length of the longest
* increasing subsequence in arr[] of size n
*/
static int lis(int[] arr, int n)
{
int max = 0;
int[] lst = new int[n];
// initialize LIS values for all indexes
Arrays.fill(lst, 1);
/* Compute optimized LIS values
in bottom up manner */
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[i] > arr[j] &&
lst[i] < lst[j] + 1)
lst[i] = lst[j] + 1;
}
}
/* Pick maximum of all LIS values */
for (int i = 0; i < n; i++)
if (max < lst[i])
max = lst[i];
return max;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.length;
System.out.println("Length of lis is " +
lis(arr, n));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Dynamic Programming python3
# implementation of LIS problem
# lis() returns the length of the
# longest increasing subsequence
# in arr[] of size n
def lis(arr, n):
i, j, maxm = 0, 0, 0
# initialize LIS values for all indexes
lst = [1 for s in range(n)]
for i in range(1, n):
for j in range(0, i):
if (arr[i] > arr[j] and
lst[i] < lst[j] + 1):
lst[i] = lst[j] + 1
# Pick maximum of all LIS values
for i in range(0, n):
if maxm < lst[i]:
maxm = lst[i]
return maxm
# Driver Code
arr = [10, 22, 9, 33, 21, 50, 41, 60]
n = len(arr)
print("Length of lst is", lis(arr, n))
# This code is contributed
# by Mohit kumar 29
C#
/* Dynamic Programming Java implementation
of LIS problem */
using System;
public class GFG
{
/*
* lis() returns the length of the longest
* increasing subsequence in arr[] of size n
*/
static int lis(int[] arr, int n)
{
int max = 0;
int[] lst = new int[n];
// initialize LIS values for all indexes
Array.Fill(lst, 1);
/* Compute optimized LIS values
in bottom up manner */
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[i] > arr[j] && lst[i] < lst[j] + 1)
{
lst[i] = lst[j] + 1;
}
}
}
/* Pick maximum of all LIS values */
for (int i = 0; i < n; i++)
if (max < lst[i])
max = lst[i];
return max;
}
// Driver code
static public void Main ()
{
int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.Length;
Console.WriteLine("Length of lis is " + lis(arr, n));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
/* Dynamic Programming Javascript implementation
of LIS problem */
/*
* lis() returns the length of the longest
* increasing subsequence in arr[] of size n
*/
function lis(arr,n)
{
let max = 0;
let lst = new Array(n);
// initialize LIS values for all indexes
for(let i=0;i<lst.length;i++)
{
lst[i]=1;
}
/* Compute optimized LIS values
in bottom up manner */
for (let i = 1; i < n; i++)
{
for (let j = 0; j < i; j++)
{
if (arr[i] > arr[j] &&
lst[i] < lst[j] + 1)
lst[i] = lst[j] + 1;
}
}
/* Pick maximum of all LIS values */
for (let i = 0; i < n; i++)
if (max < lst[i])
max = lst[i];
return max;
}
// Driver Code
let arr=[10, 22, 9, 33, 21, 50, 41, 60 ];
let n = arr.length;
document.write("Length of lis is " +
lis(arr, n));
// This code is contributed by patel2127
</script>
Length of lis is 5
Análisis de Complejidad:
Complejidad Temporal: O(n 2 ). Como se usa el bucle anidado.
Espacio Auxiliar: O(n).
Consulte el artículo completo sobre programación dinámica | ¡Establezca 3 (Subsecuencia creciente más larga) para obtener más detalles!
Método 2: enfoque basado en el límite inferior
Algoritmo:
1. Iterar la array.
2. Declare una nueva array y agregue la subsecuencia creciente recién construida.
2. Para cada índice, si lower_bound apunta al final de la array ans , introdúzcalo en un vector ans .
3. Devuelva el tamaño de la array ans .
C++
#include <bits/stdc++.h>
using namespace std;
int longest_increasing_subsequence(vector<int>& arr)
{
vector<int> ans;
int n = arr.size();
for (int i = 0; i < n; i++) {
auto it
= lower_bound(ans.begin(), ans.end(), arr[i]);
if (it == ans.end()) {
ans.push_back(arr[i]);
}
else {
*it = arr[i];
}
}
return ans.size();
}
int main()
{
vector<int> a = { 10, 22, 9, 33, 21, 50, 41, 60 };
int ans = longest_increasing_subsequence(a);
cout << ans;
return 0;
}
5
Complejidad de tiempo: O(nlogn), n = tamaño de la array.
Complejidad espacial: O(n)
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