Categoría: LIS

La suma máxima que aumenta la subsecuencia de un prefijo y un elemento dado después del prefijo es obligatoria

Posted on by Rudeus Greyrat

Dada una array de n enteros positivos, escriba un programa para encontrar la suma máxima de subsecuencias crecientes desde el prefijo hasta el i-ésimo índice y que también incluya un k-ésimo elemento dado que está después de i, es decir, k > i.  Ejemplos:   Entrada: arr[] = {1, 101, 2, 3, 100, 4, 5} i-th … Continue reading «La suma máxima que aumenta la subsecuencia de un prefijo y un elemento dado después del prefijo es obligatoria»

Construcción de la subsecuencia creciente más larga (N log N)

Posted on by Rudeus Greyrat

En mi publicación anterior, expliqué en detalle el problema de la subsecuencia creciente más larga  (LIS). 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. Lo dejo como ejercicio. Si lo has solucionado, saludos. Si no, no estás solo, aquí tienes el … Continue reading «Construcción de la subsecuencia creciente más larga (N log N)»

Subsecuencia divisoria más larga

Posted on by Rudeus Greyrat

Se le da una array A de tamaño N. Su tarea es encontrar la longitud de la subsecuencia divisoria más grande. Una secuencia divisoria es una secuencia a1, a2, …, aN donde ai divide aj siempre que i < j. Por ejemplo, 3, 15, 60, 720 es una secuencia divisoria. input:  la primera línea de cada … Continue reading «Subsecuencia divisoria más larga»

Programa C para encontrar la subsecuencia bitónica más larga

Posted on by Rudeus Greyrat

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 «Programa C para encontrar la subsecuencia bitónica más larga»