Dada una array de números aleatorios. Encuentre la subsecuencia creciente más larga (LIS) en la array. Sé que muchos de ustedes pueden haber leído soluciones de programación recursiva y dinámica (DP). Hay pocas requests de algo O(N log N) en las publicaciones del foro.
Por el momento, olvídate de las soluciones recursivas y DP. Tomemos pequeñas muestras y extendamos la solución a grandes instancias. Aunque puede parecer complejo al principio, una vez que entendemos la lógica, la codificación es simple.
Considere una array de entrada A = {2, 5, 3}. Extenderé la array durante la explicación.
Por observación sabemos que LIS es {2, 3} o {2, 5}. Tenga en cuenta que estoy considerando solo secuencias estrictamente crecientes .
Agreguemos dos elementos más, digamos 7, 11 a la array. Estos elementos ampliarán las secuencias existentes. Ahora las secuencias crecientes son {2, 3, 7, 11} y {2, 5, 7, 11} para la array de entrada {2, 5, 3, 7, 11}.
Además, agregamos un elemento más, digamos 8 a la array, es decir, la array de entrada se convierte en {2, 5, 3, 7, 11, 8}. Tenga en cuenta que el último elemento 8 es mayor que el elemento más pequeño de cualquier secuencia activa ( hablaremos en breve sobre las secuencias activas ). ¿Cómo podemos extender las secuencias existentes con 8? En primer lugar, ¿8 puede ser parte de LIS? Si es así, ¿cómo? Si queremos sumar 8, debe venir después de 7 (reemplazando 11).
Dado que el enfoque es fuera de línea (¿a qué nos referimos con fuera de línea ?) , no estamos seguros de si agregar 8 extenderá la serie o no. Suponga que hay 9 en la array de entrada, digamos {2, 5, 3, 7, 11, 8, 7, 9…}. Podemos reemplazar 11 con 8, ya que existe el mejor candidato potencial (9) que puede extender la nueva serie {2, 3, 7, 8} o {2, 5, 7, 8}.
Nuestra observación es, supongamos que el elemento final de la secuencia más grande es E. Podemos agregar (reemplazar) el elemento actual A[i] a la secuencia existente si hay un elemento A[j] (j > i) tal que E < A [i] < A[j] o (E > A[i] < A[j] – para reemplazar). En el ejemplo anterior, E = 11, A[i] = 8 y A[j] = 9.
En el caso de nuestra array original {2, 5, 3}, tenga en cuenta que nos enfrentamos a la misma situación cuando sumamos 3 para aumentar secuencia {2, 5}. Acabo de crear dos secuencias crecientes para simplificar la explicación. En lugar de dos secuencias, 3 puede reemplazar a 5 en la secuencia {2, 5}.
Sé que será confuso, ¡lo aclararé en breve!
La pregunta es, ¿cuándo será seguro agregar o reemplazar un elemento en la secuencia existente?
Consideremos otra muestra A = {2, 5, 3}. Digamos que el siguiente elemento es 1. ¿Cómo puede extender las secuencias actuales {2, 3} o {2, 5}? Obviamente, tampoco se puede extender. Sin embargo, existe la posibilidad de que el nuevo elemento más pequeño pueda ser el comienzo de un LIS. Para que quede claro, considera que la array es {2, 5, 3, 1, 2, 3, 4, 5, 6}. Hacer 1 como nueva secuencia creará una nueva secuencia que es la más grande.
La observación es que, cuando encontramos un nuevo elemento más pequeño en la array, puede ser un candidato potencial para comenzar una nueva secuencia.
A partir de las observaciones, necesitamos mantener listas de secuencias crecientes.
En general, tenemos un conjunto de listas activasde longitud variable. Estamos agregando un elemento A[i] a estas listas. Escaneamos las listas (para elementos finales) en orden decreciente de su longitud. Verificaremos los elementos finales de todas las listas para encontrar una lista cuyo elemento final sea menor que A[i] ( valor suelo ).
Nuestra estrategia determinada por las siguientes condiciones,
1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].
3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.
Tenga en cuenta que en cualquier instancia durante nuestra construcción de listas activas, se mantiene la siguiente condición.
“El elemento final de la lista más pequeña es más pequeño que los elementos finales de las listas más grandes” .
Quedará claro con un ejemplo, tomemos un ejemplo de wiki {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.
A[0] = 0. Case 1. There are no active lists, create one. 0. ----------------------------------------------------------------------------- A[1] = 8. Case 2. Clone and extend. 0. 0, 8. ----------------------------------------------------------------------------- A[2] = 4. Case 3. Clone, extend and discard. 0. 0, 4. 0, 8. Discarded ----------------------------------------------------------------------------- A[3] = 12. Case 2. Clone and extend. 0. 0, 4. 0, 4, 12. ----------------------------------------------------------------------------- A[4] = 2. Case 3. Clone, extend and discard. 0. 0, 2. 0, 4. Discarded. 0, 4, 12. ----------------------------------------------------------------------------- A[5] = 10. Case 3. Clone, extend and discard. 0. 0, 2. 0, 2, 10. 0, 4, 12. Discarded. ----------------------------------------------------------------------------- A[6] = 6. Case 3. Clone, extend and discard. 0. 0, 2. 0, 2, 6. 0, 2, 10. Discarded. ----------------------------------------------------------------------------- A[7] = 14. Case 2. Clone and extend. 0. 0, 2. 0, 2, 6. 0, 2, 6, 14. ----------------------------------------------------------------------------- A[8] = 1. Case 3. Clone, extend and discard. 0. 0, 1. 0, 2. Discarded. 0, 2, 6. 0, 2, 6, 14. ----------------------------------------------------------------------------- A[9] = 9. Case 3. Clone, extend and discard. 0. 0, 1. 0, 2, 6. 0, 2, 6, 9. 0, 2, 6, 14. Discarded. ----------------------------------------------------------------------------- A[10] = 5. Case 3. Clone, extend and discard. 0. 0, 1. 0, 1, 5. 0, 2, 6. Discarded. 0, 2, 6, 9. ----------------------------------------------------------------------------- A[11] = 13. Case 2. Clone and extend. 0. 0, 1. 0, 1, 5. 0, 2, 6, 9. 0, 2, 6, 9, 13. ----------------------------------------------------------------------------- A[12] = 3. Case 3. Clone, extend and discard. 0. 0, 1. 0, 1, 3. 0, 1, 5. Discarded. 0, 2, 6, 9. 0, 2, 6, 9, 13. ----------------------------------------------------------------------------- A[13] = 11. Case 3. Clone, extend and discard. 0. 0, 1. 0, 1, 3. 0, 2, 6, 9. 0, 2, 6, 9, 11. 0, 2, 6, 9, 13. Discarded. ----------------------------------------------------------------------------- A[14] = 7. Case 3. Clone, extend and discard. 0. 0, 1. 0, 1, 3. 0, 1, 3, 7. 0, 2, 6, 9. Discarded. 0, 2, 6, 9, 11. ---------------------------------------------------------------------------- A[15] = 15. Case 2. Clone and extend. 0. 0, 1. 0, 1, 3. 0, 1, 3, 7. 0, 2, 6, 9, 11. 0, 2, 6, 9, 11, 15. <-- LIS List ----------------------------------------------------------------------------
Es necesario comprender la estrategia anterior para diseñar un algoritmo. Además, asegúrese de haber mantenido la condición, «el elemento final de la lista más pequeña es más pequeño que los elementos finales de las listas más grandes «. Pruebe con algunos otros ejemplos, antes de seguir leyendo. Es importante entender lo que sucede con los elementos finales.
Algoritmo:
consultar la longitud más larga es bastante fácil. Tenga en cuenta que estamos tratando solo con elementos finales. No necesitamos mantener todas las listas. Podemos almacenar los elementos finales en una array. La operación de descarte se puede simular con el reemplazo, y extender una lista es análogo a agregar más elementos a la array.
Usaremos una array auxiliar para mantener los elementos finales. La longitud máxima de esta array es la de entrada. En el peor de los casos, la array se divide en N listas de tamaño uno (tenga en cuenta que no conduce a la complejidad del peor de los casos ). Para descartar un elemento, rastrearemos el valor máximo de A[i] en la array auxiliar (nuevamente observe los elementos finales en su trabajo preliminar) y reemplazaremos el valor máximo con A[i]. Extendemos una lista agregando elementos a la array auxiliar. También mantenemos un contador para realizar un seguimiento de la longitud de la array auxiliar.
Bonificación: has aprendido parcialmente la técnica de clasificación de paciencia 🙂
Aquí hay un proverbio: » Dime y lo olvidaré». Muéstramelo y lo recordaré. Involúcrame y lo entenderé ”. Entonces, elige un palo de la baraja de cartas. Encuentre la subsecuencia creciente más larga de cartas del palo barajado. Nunca olvidarás el enfoque. 🙂
Actualización – 17 julio, 2016: Respuestas bastante impresionantes de los lectores y pocos sitios que refieren la publicación, sintiéndome feliz porque mi arduo trabajo ayuda a los demás. Parece que los lectores no están haciendo ninguna tarea antes de publicar comentarios. Solicito revisar algunos ejemplos después de leer el artículo, y por favor haga su trabajo en papel (no use editor/compilador). La petición es para ayudarse a sí mismo. Profesar «saber» es diferente de la comprensión real (sin faltar el respeto). A continuación se presenta mi experiencia personal.
La preparación inicial del contenido me tomó aproximadamente 6 horas. Pero, fue una buena lección. Terminé el código inicial en una hora. Cuando empiezo a escribir contenido para explicar al lector, me doy cuenta de que no entendía los casos. Tomé mi cuaderno de notas (tengo la costumbre de mantener un cuaderno de notas encuadernado para realizar un seguimiento de mi trabajo en bruto), y después de unas pocas horas llené casi 15 páginas de trabajo en bruto. Cualquiera que sea el contenido que está viendo en el ejemplo de color gris es de estas páginas. Todo el proceso de pensamiento para la solución desenstringdo por una nota en el libro ‘Introducción a los algoritmos de Udi Manber’, recomiendo encarecidamente practicar el libro.
Sospecho que muchos lectores podrían no entender la lógica detrás de CeilIndex (búsqueda binaria). Lo dejo como ejercicio para que el lector entienda cómo funciona. Ejecute algunos ejemplos en papel. Me di cuenta de que ya había cubierto el algoritmo en otra publicación .
Actualización – 5 de agosto de 2016 :
Vale la pena consultar el siguiente enlace después de hacer su trabajo. Conocí el enlace a través de mi perfil Disqus creado recientemente. El enlace tiene una explicación del enfoque mencionado en el Wiki.
http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
A continuación se muestra el código para encontrar la longitud de LIS ( actualizado al código C++ 11, no arrays de estilo C ),
C++
#include <iostream>
#include <vector>
// Binary search (note boundaries in the caller)
int CeilIndex(std::vector<int>& v, int l, int r, int key)
{
while (r - l > 1) {
int m = l + (r - l) / 2;
if (v[m] >= key)
r = m;
else
l = m;
}
return r;
}
int LongestIncreasingSubsequenceLength(std::vector<int>& v)
{
if (v.size() == 0)
return 0;
std::vector<int> tail(v.size(), 0);
int length = 1; // always points empty slot in tail
tail[0] = v[0];
for (size_t i = 1; i < v.size(); i++) {
// new smallest value
if (v[i] < tail[0])
tail[0] = v[i];
// v[i] extends largest subsequence
else if (v[i] > tail[length - 1])
tail[length++] = v[i];
// v[i] will become end candidate of an existing
// subsequence or Throw away larger elements in all
// LIS, to make room for upcoming greater elements
// than v[i] (and also, v[i] would have already
// appeared in one of LIS, identify the location
// and replace it)
else
tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
}
return length;
}
int main()
{
std::vector<int> v{ 2, 5, 3, 7, 11, 8, 10, 13, 6 };
std::cout << "Length of Longest Increasing Subsequence is "
<< LongestIncreasingSubsequenceLength(v) << '\n';
return 0;
}
Java
// Java program to find length of longest increasing subsequence
// in O(n Log n) time
import java.io.*;
import java.util.*;
import java.lang.Math;
class LIS {
// Binary search (note boundaries in the caller)
// A[] is ceilIndex in the caller
static int CeilIndex(int A[], int l, int r, int key)
{
while (r - l > 1) {
int m = l + (r - l) / 2;
if (A[m] >= key)
r = m;
else
l = m;
}
return r;
}
static int LongestIncreasingSubsequenceLength(int A[], int size)
{
// Add boundary case, when array size is one
int[] tailTable = new int[size];
int len; // always points empty slot
tailTable[0] = A[0];
len = 1;
for (int i = 1; i < size; i++) {
if (A[i] < tailTable[0])
// new smallest value
tailTable[0] = A[i];
else if (A[i] > tailTable[len - 1])
// A[i] wants to extend largest subsequence
tailTable[len++] = A[i];
else
// A[i] wants to be current end candidate of an existing
// subsequence. It will replace ceil value in tailTable
tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];
}
return len;
}
// Driver program to test above function
public static void main(String[] args)
{
int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
int n = A.length;
System.out.println("Length of Longest Increasing Subsequence is " + LongestIncreasingSubsequenceLength(A, n));
}
}
/* This code is contributed by Devesh Agrawal*/
Python3
# Python program to find
# length of longest
# increasing subsequence
# in O(n Log n) time
# Binary search (note
# boundaries in the caller)
# A[] is ceilIndex
# in the caller
def CeilIndex(A, l, r, key):
while (r - l > 1):
m = l + (r - l)//2
if (A[m] >= key):
r = m
else:
l = m
return r
def LongestIncreasingSubsequenceLength(A, size):
# Add boundary case,
# when array size is one
tailTable = [0 for i in range(size + 1)]
len = 0 # always points empty slot
tailTable[0] = A[0]
len = 1
for i in range(1, size):
if (A[i] < tailTable[0]):
# new smallest value
tailTable[0] = A[i]
elif (A[i] > tailTable[len-1]):
# A[i] wants to extend
# largest subsequence
tailTable[len] = A[i]
len+= 1
else:
# A[i] wants to be current
# end candidate of an existing
# subsequence. It will replace
# ceil value in tailTable
tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i]
return len
# Driver program to
# test above function
A = [ 2, 5, 3, 7, 11, 8, 10, 13, 6 ]
n = len(A)
print("Length of Longest Increasing Subsequence is ",
LongestIncreasingSubsequenceLength(A, n))
# This code is contributed
# by Anant Agarwal.
C#
// C# program to find length of longest
// increasing subsequence in O(n Log n)
// time
using System;
class GFG {
// Binary search (note boundaries
// in the caller) A[] is ceilIndex
// in the caller
static int CeilIndex(int[] A, int l,
int r, int key)
{
while (r - l > 1) {
int m = l + (r - l) / 2;
if (A[m] >= key)
r = m;
else
l = m;
}
return r;
}
static int LongestIncreasingSubsequenceLength(
int[] A, int size)
{
// Add boundary case, when array size
// is one
int[] tailTable = new int[size];
int len; // always points empty slot
tailTable[0] = A[0];
len = 1;
for (int i = 1; i < size; i++) {
if (A[i] < tailTable[0])
// new smallest value
tailTable[0] = A[i];
else if (A[i] > tailTable[len - 1])
// A[i] wants to extend largest
// subsequence
tailTable[len++] = A[i];
else
// A[i] wants to be current end
// candidate of an existing
// subsequence. It will replace
// ceil value in tailTable
tailTable[CeilIndex(tailTable, -1,
len - 1, A[i])]
= A[i];
}
return len;
}
// Driver program to test above function
public static void Main()
{
int[] A = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
int n = A.Length;
Console.Write("Length of Longest "
+ "Increasing Subsequence is " + LongestIncreasingSubsequenceLength(A, n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find
// length of longest
// increasing subsequence
// in O(n Log n) time
// Binary search (note
// boundaries in the caller)
// A[] is ceilIndex
// in the caller
function CeilIndex($A, $l, $r, $key)
{
while ($r - $l > 1)
{
$m = (int)($l + ($r - $l)/2);
if ($A[$m] >= $key)
$r = $m;
else
$l = $m;
}
return $r;
}
function LongestIncreasingSubsequenceLength($A, $size)
{
// Add boundary case,
// when array size is one
$tailTable = array_fill(0, ($size + 1), 0);
$len = 0; // always points empty slot
$tailTable[0] = $A[0];
$len = 1;
for($i = 1; $i < $size; $i++)
{
if ($A[$i] < $tailTable[0])
// new smallest value
$tailTable[0] = $A[$i];
else if ($A[$i] > $tailTable[$len-1])
{
// A[i] wants to extend
// largest subsequence
$tailTable[$len] = $A[$i];
$len++;
}
else
// A[i] wants to be current
// end candidate of an existing
// subsequence. It will replace
// ceil value in tailTable
$tailTable[CeilIndex($tailTable, -1, $len-1, $A[$i])] = $A[$i];
}
return $len;
}
// Driver program to
// test above function
$A = array( 2, 5, 3, 7, 11, 8, 10, 13, 6 );
$n = count($A);
print("Length of Longest Increasing Subsequence is ".
LongestIncreasingSubsequenceLength($A, $n));
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// javascript program to find length of longest increasing subsequence
// in O(n Log n) time
// Binary search (note boundaries in the caller)
// A is ceilIndex in the caller
function CeilIndex(A , l , r , key) {
while (r - l > 1) {
var m = l + parseInt((r - l) / 2);
if (A[m] >= key)
r = m;
else
l = m;
}
return r;
}
function LongestIncreasingSubsequenceLength(A , size)
{
// Add boundary case, when array size is one
var tailTable = Array(size).fill(0);
var len; // always points empty slot
tailTable[0] = A[0];
len = 1;
for (var i = 1; i < size; i++) {
if (A[i] < tailTable[0])
// new smallest value
tailTable[0] = A[i];
else if (A[i] > tailTable[len - 1])
// A[i] wants to extend largest subsequence
tailTable[len++] = A[i];
else
// A[i] wants to be current end candidate of an existing
// subsequence. It will replace ceil value in tailTable
tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];
}
return len;
}
// Driver program to test above function
var A = [ 2, 5, 3, 7, 11, 8, 10, 13, 6 ];
var n = A.length;
document.write("Length of Longest Increasing Subsequence is " + LongestIncreasingSubsequenceLength(A, n));
// This code is contributed by gauravrajput1
</script>
Producción:
Length of Longest Increasing Subsequence is 6
Complejidad:
el bucle se ejecuta para N elementos. En el peor de los casos (¿cuál es la entrada del peor de los casos?), podemos terminar consultando el valor del techo mediante la búsqueda binaria (log i ) para muchos A[i].
Por lo tanto, T(n) < O(log N! ) = O(N log N). Analice para asegurarse de que los límites superior e inferior también sean O( N log N ). La complejidad es THETA (N log N).
Ejercicios:
1. Diseñar un algoritmo para construir la lista creciente más larga . Además, modele su solución usando DAG.
2. Diseñe un algoritmo para construir todas las listas crecientes del mismo tamaño más largo .
3. ¿El algoritmo anterior es un algoritmo en línea ?
4. Diseñe un algoritmo para construir la decreciente más largalist.. A continuación
se proporciona una implementación alternativa en varios idiomas utilizando sus funciones de búsqueda binaria integradas:
CPP
#include <bits/stdc++.h>
using namespace std;
int LongestIncreasingSubsequenceLength(std::vector<int>& v)
{
if (v.size() == 0) // boundary case
return 0;
std::vector<int> tail(v.size(), 0);
int length = 1; // always points empty slot in tail
tail[0] = v[0];
for (int i = 1; i < v.size(); i++) {
// Do binary search for the element in
// the range from begin to begin + length
auto b = tail.begin(), e = tail.begin() + length;
auto it = lower_bound(b, e, v[i]);
// If not present change the tail element to v[i]
if (it == tail.begin() + length)
tail[length++] = v[i];
else
*it = v[i];
}
return length;
}
int main()
{
std::vector<int> v{ 2, 5, 3, 7, 11, 8, 10, 13, 6 };
std::cout
<< "Length of Longest Increasing Subsequence is "
<< LongestIncreasingSubsequenceLength(v);
return 0;
}
Java
import java.io.*;
import java.lang.Math;
import java.util.*;
class LIS {
static int LongestIncreasingSubsequenceLength(int v[])
{
if (v.length == 0) // boundary case
return 0;
int[] tail = new int[v.length];
int length = 1; // always points empty slot in tail
tail[0] = v[0];
for (int i = 1; i < v.length; i++) {
if (v[i] > tail[length - 1]) {
// v[i] extends the largest subsequence
tail[length++] = v[i];
}
else {
// v[i] will extend a subsequence and
// discard older subsequence
// find the largest value just smaller than
// v[i] in tail
// to find that value do binary search for
// the v[i] in the range from begin to 0 +
// length
int idx = Arrays.binarySearch(
tail, 0, length - 1, v[i]);
// binarySearch in java returns negative
// value if searched element is not found in
// array
// this negative value stores the
// appropriate place where the element is
// supposed to be stored
if (idx < 0)
idx = -1 * idx - 1;
// replacing the existing subsequence with
// new end value
tail[idx] = v[i];
}
}
return length;
}
// Driver program to test above function
public static void main(String[] args)
{
int v[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
System.out.println(
"Length of Longest Increasing Subsequence is "
+ LongestIncreasingSubsequenceLength(v));
}
}
/* This code is contributed by Serjeel Ranjan */
Python3
from bisect import bisect_left
def LongestIncreasingSubsequenceLength(v):
if len(v) == 0: # boundary case
return 0
tail = [0 for i in range(len(v) + 1)]
length = 1 # always points empty slot in tail
tail[0] = v[0]
for i in range(1, len(v)):
if v[i] > tail[length-1]:
# v[i] extends the largest subsequence
tail[length] = v[i]
length += 1
else:
# v[i] will extend a subsequence and discard older subsequence
# find the largest value just smaller than v[i] in tail
# to find that value do binary search for the v[i] in
# the range from begin to 0 + length
# bisect function either returns index where element is found
# or the appropriate index at which element should be placed
# finally replace the existing subsequence with new end value
tail[bisect_left(tail, v[i], 0, length-1)] = v[i]
return length
# Driver program to test above function
v = [2, 5, 3, 7, 11, 8, 10, 13, 6]
print("Length of Longest Increasing Subsequence is ",
LongestIncreasingSubsequenceLength(v))
# This code is contributed by Serjeel Ranjan
C#
using System;
using System.Collections.Generic;
public class LIS {
public
static int lowerBound(int[] a, int low, int high, int element){
while(low < high){
int middle = low + (high - low)/2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int longestIncreasingSubsequenceLength(int []v)
{
if (v.GetLength(0) == 0) // boundary case
return 0;
int[] tail = new int[v.GetLength(0)];
int length = 1; // always points empty slot in tail
tail[0] = v[0];
for (int i = 1; i < v.GetLength(0); i++) {
if (v[i] > tail[length -1])
{
// v[i] extends the largest subsequence
tail[length++] = v[i];
}
else
{
// v[i] will extend a subsequence and
// discard older subsequence
// find the largest value just smaller than
// v[i] in tail
// to find that value do binary search for
// the v[i] in the range from begin to 0 +
// length
int idx = lowerBound(v, 1, v.GetLength(0), v[i]);
// binarySearch in C# returns negative
// value if searched element is not found in
// array
// this negative value stores the
// appropriate place where the element is
// supposed to be stored
if (idx < 0)
idx = -1 * idx -1;
// replacing the existing subsequence with
// new end value
tail[idx] = v[i];
}
}
return length;
}
// Driver program to test above function
public static void Main(String[] args)
{
int []v = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
Console.WriteLine(
"Length of longest Increasing Subsequence is "
+ (longestIncreasingSubsequenceLength(v)+1));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
function lowerBound(a , low , high , element){
while(low < high){
var middle = low + (high - low)/2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
function longestIncreasingSubsequenceLength(v)
{
if (v.length == 0) // boundary case
return 0;
var tail = Array(v.length).fill(0);
var length = 1; // always points empty slot in tail
tail[0] = v[0];
for (i = 1; i < v.length; i++) {
if (v[i] > tail[length -1])
{
// v[i] extends the largest subsequence
tail[length++] = v[i];
}
else
{
// v[i] will extend a subsequence and
// discard older subsequence
// find the largest value just smaller than
// v[i] in tail
// to find that value do binary search for
// the v[i] in the range from begin to 0 +
// length
var idx = lowerBound(v, 1, v.length, v[i]);
// binarySearch in C# returns negative
// value if searched element is not found in
// array
// this negative value stores the
// appropriate place where the element is
// supposed to be stored
if (idx < 0)
idx = -1 * idx -1;
// replacing the existing subsequence with
// new end value
tail[idx] = v[i];
}
}
return length;
}
// Driver program to test above function
var v = [ 2, 5, 3, 7, 11, 8, 10, 13, 6 ];
document.write(
"Length of longest Increasing Subsequence is "
+ (longestIncreasingSubsequenceLength(v)+1));
// This code is contributed by gauravrajput1
</script>
Producción:
Length of Longest Increasing Subsequence is 6
— Venki . 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