Subsecuencia bitónica más larga | DP-15 – Part 1

Dada una array arr[0 … n-1] que contiene n enteros positivos, una subsecuencia de arr[] se llama bitónica si primero es creciente y luego decreciente. Escriba una función que tome una array como argumento y devuelva la longitud de la subsecuencia bitónica más larga. Una secuencia ordenada en orden creciente se considera bitónica con la parte … Continue reading «Subsecuencia bitónica más larga | DP-15 – Part 1»

Teorema de Dilworth

Sea S un conjunto finito parcialmente ordenado . El tamaño de una antistring máxima es igual al tamaño de una cobertura de string mínima de S . Esto se llama el teorema de Dilworth . Lleva el nombre del matemático Robert P. Dilworth (1950). El ancho de un conjunto finito parcialmente ordenado S es el … Continue reading «Teorema de Dilworth»

Longitud de la subsecuencia creciente más larga que no contiene una secuencia dada como subarreglo

Dados dos arreglos arr[] y arr1[] de longitudes N y M respectivamente, la tarea es encontrar la subsecuencia creciente más larga del arreglo arr[] tal que no contenga el arreglo arr1[] como subarreglo . Ejemplos: Entrada: arr[] = {5, 3, 9, 3, 4, 7}, arr1[] = {3, 3, 7} Salida: 4 Explicación: La subsecuencia creciente … Continue reading «Longitud de la subsecuencia creciente más larga que no contiene una secuencia dada como subarreglo»

Número mínimo de eliminaciones para hacer una secuencia ordenada

Dada una array de n enteros. La tarea es eliminar o eliminar el número mínimo de elementos de la array para que cuando los elementos restantes se coloquen en el mismo orden de secuencia para formar una secuencia ordenada creciente . Ejemplos:   Input : {5, 6, 1, 7, 4} Output : 2 Removing 1 and … Continue reading «Número mínimo de eliminaciones para hacer una secuencia ordenada»

Subsecuencia creciente más larga que consta de elementos de índices divisibles por índices seleccionados previamente

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la longitud de la subsecuencia creciente más larga posible seleccionando elementos de índices que son divisibles por todos los índices seleccionados previamente. Nota: considere la indexación basada en 1 Ejemplos: Entrada: arr[] = {1, 4, 2, 3, 6, 4, 9} Salida: 3 … Continue reading «Subsecuencia creciente más larga que consta de elementos de índices divisibles por índices seleccionados previamente»

Subsecuencia decreciente de suma máxima

Dada una array de N enteros positivos. La tarea es encontrar la suma de la subsecuencia decreciente de suma máxima (MSDS) de la array dada de modo que los enteros en la subsecuencia se clasifiquen en orden decreciente. Ejemplos :  Entrada: arr[] = {5, 4, 100, 3, 2, 101, 1}  Salida: 106  100 + 3 + … Continue reading «Subsecuencia decreciente de suma máxima»

Concatenación mínima requerida para obtener estrictamente LIS para arreglos con elementos repetitivos | Conjunto-2

Dada una array A[] de tamaño n donde puede haber elementos repetitivos en la array. Tenemos que encontrar la concatenación mínima requerida para que la secuencia A obtenga estrictamente la subsecuencia creciente más larga. Para la array A[] seguimos la indexación basada en 1. Ejemplos: Entrada: A = {2, 1, 2, 4, 3, 5}  Salida: … Continue reading «Concatenación mínima requerida para obtener estrictamente LIS para arreglos con elementos repetitivos | Conjunto-2»

Tamaño de la array después de la eliminación repetida de LIS

Dada una array arr[0..n-1] del elemento positivo. La tarea es imprimir los elementos restantes de arr[] después de la eliminación repetida de LIS (de tamaño superior a 1). Si hay varios LIS con la misma longitud, debemos elegir el LIS que termina primero. Ejemplos:  Input : arr[] = {1, 2, 5, 3, 6, 4, 1} … Continue reading «Tamaño de la array después de la eliminación repetida de LIS»

Programa Java para la subsecuencia creciente más larga

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 … Continue reading «Programa Java para la subsecuencia creciente más larga»

Genere una permutación de longitud N que tenga LIS de igual tamaño desde ambos extremos

Dado un número entero N , la tarea es generar una permutación de elementos en el rango [1, N] en tal orden que la longitud de LIS desde el inicio sea igual a LIS desde el final de la array. Imprime -1 si no existe tal array. Ejemplos: Entrada: N = 5 Salida: [1, 3, … Continue reading «Genere una permutación de longitud N que tenga LIS de igual tamaño desde ambos extremos»