Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Subsecuencia creciente más larga (LIS)

Una LIS es la subsecuencia estrictamente creciente más larga que conserva el orden de entrada sin exigir que los elementos sean adyacentes. El ejemplo en C calcula su longitud mediante programación dinámica en O(n²) tiempo y con O(n) espacio auxiliar.

Versión: C23; repository compiler flag, production runtime not attested

Sintaxis

dp[i] = max({1} union {dp[j] + 1 | 0 <= j < i and a[j] < a[i]}); LIS length = n == 0 ? 0 : max(dp)

Una longest increasing subsequence (LIS), o subsecuencia creciente más larga, selecciona elementos en su orden original. Se pueden omitir elementos; la selección no tiene por qué ser contigua. Para {3, 1, 2, 2, 4}, la subsecuencia {1, 2, 4} tiene la longitud máxima 3. Ordenar la entrada cambiaría el problema, ya que se perdería el orden original.

La distinción strictly increasing versus non-decreasing significa que una subsecuencia estrictamente creciente requiere <, mientras que una no decreciente permite <=. Los valores iguales no alargan una LIS. Al sustituir a[j] < a[i] por a[j] <= a[i], se obtiene un algoritmo para la subsecuencia no decreciente más larga; su longitud para los datos del ejemplo es 4.

Sea dp[i] la longitud de la mejor subsecuencia que termina exactamente en a[i]. Inicialízala en 1. Para cada j < i que cumpla a[j] < a[i], considera dp[j] + 1. Calcula los estados de izquierda a derecha y conserva el resultado mayor. Los bucles anidados requieren O(n²) tiempo, y el array dp usa O(n) espacio auxiliar.

El ejemplo devuelve solo la longitud. Guardar los índices de los predecesores es opcional: si la entrada no está vacía, puedes reconstruir una LIS a partir de a y dp. Empieza por seleccionar a[i] en un índice i donde dp[i] sea máximo. Recorre los índices hacia atrás y selecciona a[j] cuando se cumplan j < i, a[j] < a[i] y dp[j] + 1 == dp[i]. Tras cada selección, actualiza i a j. Detente cuando dp[i] == 1 e invierte el orden de los elementos seleccionados.

Quien llama proporciona arrays a y dp que no se solapan y que contienen al menos n elementos cada uno. Si n == 0, la función devuelve 0 sin acceder a ninguno de los arrays, por lo que se permite NULL. No utiliza ni asignación dinámica ni arrays de longitud variable.

Ejemplos

#include <stddef.h>
#include <stdio.h>

/* For n > 0, a and dp must each provide at least n elements.
   Their storage must not overlap. For n == 0, both may be NULL. */
static size_t lis_length(const int *a, size_t n, size_t *dp)
{
    size_t best = 0;
    for (size_t i = 0; i < n; ++i) {
        dp[i] = 1;
        for (size_t j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > best) {
            best = dp[i];
        }
    }
    return best;
}

int main(void)
{
    const int a[] = {3, 1, 2, 2, 4};
    size_t dp[sizeof a / sizeof a[0]];
    printf("LIS length: %zu\n", lis_length(a, sizeof a / sizeof a[0], dp));
    printf("Empty length: %zu\n", lis_length(NULL, 0, NULL));
    return 0;
}

Resultado

LIS length: 3
Empty length: 0

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes