Categoría: LIS

Subsecuencia común más larga de dos arrays, de las cuales una array consta solo de elementos distintos

Posted on by Rudeus Greyrat

Dadas dos arrays firstArr[] , que consisten solo en elementos distintos, y secondArr[] , la tarea es encontrar la longitud de LCS entre estas 2 arrays. Ejemplos: Entrada: firstArr[] = {3, 5, 1, 8}, secondArr[] = {3, 3, 5, 3, 8} Salida: 3. Explicación: LCS entre estas dos arrays es {3, 5, 8} . Entrada … Continue reading «Subsecuencia común más larga de dos arrays, de las cuales una array consta solo de elementos distintos»

Variaciones de LIS | DP-21 – Part 1

Posted on by Rudeus Greyrat

Hemos discutido la solución de programación dinámica para el problema de la subsecuencia creciente más larga en esta publicación y una solución O (nLogn) en esta publicación. Las siguientes son variaciones comúnmente solicitadas del problema LIS estándar .  1. Construyendo puentes: Considere un mapa 2-D con un río horizontal que pasa por su centro. Hay … Continue reading «Variaciones de LIS | DP-21 – Part 1»

Construcción de la subsecuencia creciente más larga (LIS) e impresión de la secuencia LIS

Posted on by Rudeus Greyrat

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 … Continue reading «Construcción de la subsecuencia creciente más larga (LIS) e impresión de la secuencia LIS»

Programación Dinámica | Construyendo puentes

Posted on by Rudeus Greyrat

Considere un mapa 2-D con un río horizontal que pasa por su centro. Hay n ciudades en la orilla sur con coordenadas x a(1) … a(n) y n ciudades en la orilla norte con coordenadas x b(1) … b(n). Desea conectar tantos pares de ciudades norte-sur como sea posible con puentes de modo que no … Continue reading «Programación Dinámica | Construyendo puentes»

Tamaño de subsecuencia monótonamente creciente más largo (N log N): Implementación simple

Posted on by Rudeus Greyrat

Dada una array de números aleatorios, encuentre la subsecuencia creciente monótonamente más larga (LIS) en la array. Si desea comprender el enfoque O (NlogN), se explica muy claramente aquí . En esta publicación, se analiza una implementación simple y que ahorra tiempo del enfoque O (NlogN) utilizando stl. A continuación se muestra el código para … Continue reading «Tamaño de subsecuencia monótonamente creciente más largo (N log N): Implementación simple»

LIS utilizando el árbol de segmentos

Posted on by Rudeus Greyrat

Se le da una array de números enteros, necesita encontrar la longitud de la subsecuencia creciente más larga. Puede haber 4 enfoques para resolver el problema. 1) Fuerza bruta:  en este enfoque, intentamos encontrar todas las subsecuencias crecientes y luego devolver la longitud máxima de la subsecuencia creciente más larga. Para hacer esto, hacemos uso … Continue reading «LIS utilizando el árbol de segmentos»

Subsecuencia creciente más larga | DP-3 – Part 1

Posted on by Rudeus Greyrat

Ya hemos discutido los subproblemas superpuestos y las propiedades de la subestructura óptima . Ahora, analicemos el problema de la subsecuencia creciente más larga (LIS) como un problema de ejemplo que se puede resolver mediante la programación dinámica.  El problema de la subsecuencia creciente más larga (LIS) es encontrar la longitud de la subsecuencia más larga … Continue reading «Subsecuencia creciente más larga | DP-3 – Part 1»

Programación ponderada de trabajos | Conjunto 2 (usando LIS)

Posted on by Rudeus Greyrat

Dados N trabajos donde cada trabajo está representado por los siguientes tres elementos. 1. Hora de inicio  2. Hora de finalización  3. Beneficio o valor asociado Encuentre el subconjunto de trabajos de beneficio máximo tal que no haya dos trabajos en el subconjunto que se superpongan. Ejemplos:   Input: Number of Jobs n = 4 Job … Continue reading «Programación ponderada de trabajos | Conjunto 2 (usando LIS)»

Minimice los elementos que se agregarán a una array dada de modo que contenga otra array dada como su subsecuencia | conjunto 2

Posted on by Rudeus Greyrat

Dada una array A[] que consta de N enteros distintos y otra array B[] que consta de M enteros, la tarea es encontrar el número mínimo de elementos que se agregarán a la array B[] de modo que la array A[] se convierta en el subsecuencia de la array B[] . Ejemplos: Entrada: N = … Continue reading «Minimice los elementos que se agregarán a una array dada de modo que contenga otra array dada como su subsecuencia | conjunto 2»

Número mínimo de subsecuencias crecientes

Posted on by Rudeus Greyrat

Dada una array de números enteros de tamaño N, debe dividirla en el número mínimo de «subsecuencias estrictamente crecientes».  Por ejemplo: sea la secuencia {1, 3, 2, 4}, entonces la respuesta sería 2. En este caso, la primera secuencia creciente sería {1, 3, 4} y la segunda sería {2}. Ejemplos:  Entrada: arr[] = {1 3 … Continue reading «Número mínimo de subsecuencias crecientes»