Código Java:
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}.
C++
#include <bits/stdc++.h>
using namespace std;
void LIS(int a[], int n)
{
vector<int> list;
vector<int> longestlist;
// Highest count
int hc = 0;
// Current max
int cm;
for(int i = 0; i < n; i++)
{
cm = INT_MIN;
for(int j = i; j < n; j++)
{
if (a[j] > cm)
{
list.push_back(a[j]);
cm = a[j];
}
}
// Compare previous highest subsequence
if (hc < list.size())
{
hc = list.size();
for(int k = 0; k < list.size(); k++)
{
longestlist.push_back(list[k]);
}
}
list.clear();
}
for(int i = 0; i < longestlist.size(); i++)
{
cout << longestlist[i] << ' ';
}
cout << endl;
cout << "length of longestlist is " << hc;
}
// Driver code
int main()
{
int a[] = { 10, 22, 9, 33, 21,
50, 41, 60, 80 };
int n = sizeof(a) / sizeof(a[0]);
LIS(a, n);
return 0;
}
// This code is contributed by Harshit Srivastava
Java
package BIT;
import java.util.ArrayList;
import java.util.Iterator;
public class LongestIncreasingSubsequence {
public static void main(String[] args) {
// int array[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
// int array[] = {10, 2, 9, 3, 5, 4, 6, 8};
int array[] = {10, 9, 8, 6, 5, 4};
ArrayList list = new ArrayList();
ArrayList longestList = new ArrayList();
int currentMax;
int highestCount = 0;
for(int i = 0; i < array.length;i++)
{
currentMax = Integer.MIN_VALUE;
for(int j = i;j < array.length; j++)
{
if(array[j] > currentMax)
{
list.add(array[j]);
currentMax = array[j];
}
}
//Compare previous highest subsequence
if(highestCount < list.size())
{
highestCount = list.size();
longestList = new ArrayList(list);
}
list.clear();
}
System.out.println();
//Print list
Iterator itr = longestList.iterator();
System.out.println("The Longest subsequence");
while(itr.hasNext())
{
System.out.print(itr.next() + " ");
}
System.out.println();
System.out.println("Length of LIS: " + highestCount);
}
}
Python3
import sys
def LIS(a, n):
list = []
longestlist = []
# Highest count
hc = 0
# Current max
for i in range(n):
cm = -sys.maxsize -1
for j in range(i,n):
if (a[j] > cm):
list.append(a[j])
cm = a[j]
# Compare previous highest subsequence
if (hc < len(list)):
hc = len(list)
for k in range(len(list)):
longestlist.append(list[k])
list = []
for i in range(len(longestlist)):
print(longestlist[i] ,end = ' ')
print()
print("length of longestlist is " + str(hc))
# Driver code
a = [ 10, 22, 9, 33, 21, 50, 41, 60, 80 ]
n = len(a)
LIS(a, n)
# This code is contributed by shinjanpatra
C#
using System;
using System.Collections.Generic;
class longestIncreasingSubsequence
{
public static void Main(String[] args)
{
int []array = {10, 22, 9, 33, 21, 50, 41, 60, 80};
// int []array = {10, 2, 9, 3, 5, 4, 6, 8};
//int []array = {10, 9, 8, 6, 5, 4};
List<int> list = new List<int>();
List<int> longestList = new List<int>();
int currentMax;
int highestCount = 0;
for(int i = 0; i < array.Length;i++)
{
currentMax = int.MinValue;
for(int j = i;j < array.Length; j++)
{
if(array[j] > currentMax)
{
list.Add(array[j]);
currentMax = array[j];
}
}
// Compare previous highest subsequence
if(highestCount < list.Count)
{
highestCount = list.Count;
longestList = new List<int>(list);
}
list.Clear();
}
Console.WriteLine();
// Print list
Console.WriteLine("The longest subsequence");
foreach(int itr in longestList)
{
Console.Write(itr + " ");
}
Console.WriteLine();
Console.WriteLine("Length of LIS: " + highestCount);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
function LIS(a, n)
{
let list = [];
let longestlist = [];
// Highest count
let hc = 0;
// Current max
let cm;
for(let i = 0; i < n; i++)
{
cm = Number.MIN_VALUE;
for(let j = i; j < n; j++)
{
if (a[j] > cm)
{
list.push(a[j]);
cm = a[j];
}
}
// Compare previous highest subsequence
if (hc < list.length)
{
hc = list.length;
for(let k = 0; k < list.length; k++)
{
longestlist.push(list[k]);
}
}
list = [];
}
for(let i = 0; i < longestlist.length; i++)
{
document.write(longestlist[i] + ' ');
}
document.write("</br>")
document.write("length of longestlist is " + hc);
}
// Driver code
let a = [ 10, 22, 9, 33, 21, 50, 41, 60, 80 ];
let n = a.length;
LIS(a, n);
// This code is contributed by shinjanpatra
</script>
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.
Ejemplos:
Input: [10, 22, 9, 33, 21, 50, 41, 60, 80] Output: [10, 22, 33, 50, 60, 80] OR [10 22 33 41 60 80] or any other LIS of same length.
En la publicación anterior , hemos discutido el problema de la subsecuencia creciente más larga. Sin embargo, la publicación solo cubrió el código relacionado con el tamaño de consulta de LIS, pero no la construcción de LIS. En esta publicación, discutiremos cómo imprimir LIS usando una solución DP similar discutida anteriormente.
Sea arr[0..n-1] la array de entrada. Definimos el vector L tal que L[i] es en sí mismo un vector que almacena LIS de arr que termina en arr[i]. Por ejemplo, para la array [3, 2, 6, 4, 5, 1],
L[0]: 3 L[1]: 2 L[2]: 2 6 L[3]: 2 4 L[4]: 2 4 5 L[5]: 1
Por lo tanto, para el índice i, L[i] puede escribirse recursivamente como –
L[0] = {arr[O]}
L[i] = {Max(L[j])} + arr[i]
where j < i and arr[j] < arr[i] and if there is no such j then L[i] = arr[i]
A continuación se muestra la implementación de la idea anterior:
C++
/* Dynamic Programming solution to construct Longest
Increasing Subsequence */
#include <iostream>
#include <vector>
using namespace std;
// Utility function to print LIS
void printLIS(vector<int>& arr)
{
for (int x : arr)
cout << x << " ";
cout << endl;
}
// Function to construct and print Longest Increasing
// Subsequence
void constructPrintLIS(int arr[], int n)
{
// L[i] - The longest increasing sub-sequence
// ends with arr[i]
vector<vector<int> > L(n);
// L[0] is equal to arr[0]
L[0].push_back(arr[0]);
// start from index 1
for (int i = 1; i < n; i++)
{
// do for every j less than i
for (int j = 0; j < i; j++)
{
/* L[i] = {Max(L[j])} + arr[i]
where j < i and arr[j] < arr[i] */
if ((arr[i] > arr[j]) &&
(L[i].size() < L[j].size() + 1))
L[i] = L[j];
}
// L[i] ends with arr[i]
L[i].push_back(arr[i]);
}
// L[i] now stores increasing sub-sequence of
// arr[0..i] that ends with arr[i]
vector<int> max = L[0];
// LIS will be max of all increasing sub-
// sequences of arr
for (vector<int> x : L)
if (x.size() > max.size())
max = x;
// max will contain LIS
printLIS(max);
}
// Driver function
int main()
{
int arr[] = { 3, 2, 6, 4, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// construct and print LIS of arr
constructPrintLIS(arr, n);
return 0;
}
Java
// Java program for
// the above approach
// Dynamic Programming
// solution to conLongest
// Increasing Subsequence
import java.util.*;
class GFG{
// Utility function to print LIS
static void printLIS(Vector<Integer> arr)
{
for (int x : arr)
System.out.print(x + " ");
System.out.println();
}
// Function to conand print
// Longest Increasing Subsequence
static void constructPrintLIS(int arr[],
int n)
{
// L[i] - The longest increasing
// sub-sequence ends with arr[i]
Vector<Integer> L[] = new Vector[n];
for (int i = 0; i < L.length; i++)
L[i] = new Vector<Integer>();
// L[0] is equal to arr[0]
L[0].add(arr[0]);
// Start from index 1
for (int i = 1; i < n; i++)
{
// Do for every j less than i
for (int j = 0; j < i; j++)
{
//L[i] = {Max(L[j])} + arr[i]
// where j < i and arr[j] < arr[i]
if ((arr[i] > arr[j]) &&
(L[i].size() < L[j].size() + 1))
L[i] = (Vector<Integer>) L[j].clone(); //deep copy
}
// L[i] ends with arr[i]
L[i].add(arr[i]);
}
// L[i] now stores increasing sub-sequence of
// arr[0..i] that ends with arr[i]
Vector<Integer> max = L[0];
// LIS will be max of all increasing sub-
// sequences of arr
for (Vector<Integer> x : L)
if (x.size() > max.size())
max = x;
// max will contain LIS
printLIS(max);
}
// Driver function
public static void main(String[] args)
{
int arr[] = {3, 2, 4, 5, 1};
int n = arr.length;
// print LIS of arr
constructPrintLIS(arr, n);
}
}
// This code is contributed by gauravrajput1
Python3
# Dynamic Programming solution to construct Longest
# Increasing Subsequence
# Utility function to print LIS
def printLIS(arr: list):
for x in arr:
print(x, end=" ")
print()
# Function to construct and print Longest Increasing
# Subsequence
def constructPrintLIS(arr: list, n: int):
# L[i] - The longest increasing sub-sequence
# ends with arr[i]
l = [[] for i in range(n)]
# L[0] is equal to arr[0]
l[0].append(arr[0])
# start from index 1
for i in range(1, n):
# do for every j less than i
for j in range(i):
# L[i] = {Max(L[j])} + arr[i]
# where j < i and arr[j] < arr[i]
if arr[i] > arr[j] and (len(l[i]) < len(l[j]) + 1):
l[i] = l[j].copy()
# L[i] ends with arr[i]
l[i].append(arr[i])
# L[i] now stores increasing sub-sequence of
# arr[0..i] that ends with arr[i]
maxx = l[0]
# LIS will be max of all increasing sub-
# sequences of arr
for x in l:
if len(x) > len(maxx):
maxx = x
# max will contain LIS
printLIS(maxx)
# Driver Code
if __name__ == "__main__":
arr = [3, 2, 6, 4, 5, 1]
n = len(arr)
# construct and print LIS of arr
constructPrintLIS(arr, n)
# This code is contributed by
# sanjeev2552
C#
// Dynamic Programming solution to construct Longest
// Increasing Subsequence
using System;
using System.Collections.Generic;
class GFG
{
// Utility function to print LIS
static void printLIS(List<int> arr)
{
foreach(int x in arr)
{
Console.Write(x + " ");
}
Console.WriteLine();
}
// Function to construct and print Longest Increasing
// Subsequence
static void constructPrintLIS(int[] arr, int n)
{
// L[i] - The longest increasing sub-sequence
// ends with arr[i]
List<List<int>> L = new List<List<int>>();
for(int i = 0; i < n; i++)
{
L.Add(new List<int>());
}
// L[0] is equal to arr[0]
L[0].Add(arr[0]);
// start from index 1
for (int i = 1; i < n; i++)
{
// do for every j less than i
for (int j = 0; j < i; j++)
{
/* L[i] = {Max(L[j])} + arr[i]
where j < i and arr[j] < arr[i] */
if ((arr[i] > arr[j]) && (L[i].Count < L[j].Count + 1))
L[i] = L[j];
}
// L[i] ends with arr[i]
L[i].Add(arr[i]);
}
// L[i] now stores increasing sub-sequence of
// arr[0..i] that ends with arr[i]
List<int> max = L[0];
// LIS will be max of all increasing sub-
// sequences of arr
foreach(List<int> x in L)
{
if (x.Count > max.Count)
{
max = x;
}
}
// max will contain LIS
printLIS(max);
}
// Driver code
static void Main()
{
int[] arr = { 3, 2, 4, 5, 1 };
int n = arr.Length;
// construct and print LIS of arr
constructPrintLIS(arr, n);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program Dynamic Programming solution to construct Longest
// Increasing Subsequence
function printLIS( x)
{
document.write(x+" ");
}
// Function to construct and print Longest Increasing
// Subsequence
function constructPrintLIS( arr, n)
{
// L[i] - The longest increasing sub-sequence
// ends with arr[i]
var L = new Array(n);
for(var i = 0; i < n;i++){
L[i] = [];
}
// L[0] is equal to arr[0]
L[0].push(arr[0]);
// start from index 1
for (var i = 1; i < n; i++)
{
// do for every j less than i
for (var j = 0; j < i; j++)
{
/* L[i] = {Max(L[j])} + arr[i]
where j < i and arr[j] < arr[i] */
if ((arr[i] > arr[j]) && (L[i].length< L[j].length + 1))
L[i] = [...L[j]];
}
// L[i] ends with arr[i]
L[i].push(arr[i]);
}
// L[i] now stores increasing sub-sequence of
// arr[0..i] that ends with arr[i]
var max = 0;
// LIS will be max of all increasing sub-
// sequences of arr
for (var x=0; x < L.length;x++){
if (L[x].length> L[max].length)
max = x;
}
// L[max] will contain LIS
L[max].forEach(printLIS);
}
var arr = [3, 2, 6, 4, 5, 1 ];
var n = 6;
// construct and print LIS of arr
constructPrintLIS(arr, n);
</script>
Producción:
2 4 5
Tenga en cuenta que la complejidad de tiempo de la solución de programación dinámica (DP) anterior es O (n ^ 3) (n ^ 2 para dos bucles anidados y n para copiar otro vector en un vector, por ejemplo: L [i] = L [j] contribuye O (n) también) y la complejidad del espacio es O (n ^ 2) ya que estamos usando un vector 2d para almacenar nuestro LIS y hay una solución O (n Log n) no DP para el problema LIS. Consulte la publicación a continuación para la solución O (n Log n).
Construcción de la subsecuencia monótonamente creciente más larga (N log N)
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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