Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C

Subsequência crescente mais longa (LIS)

Uma LIS é a subsequência estritamente crescente mais longa que preserva a ordem de entrada sem exigir que os elementos sejam adjacentes. O exemplo em C calcula o seu comprimento através de programação dinâmica, em O(n²) tempo e com O(n) espaço auxiliar.

Versão: C23; repository compiler flag, production runtime not attested

Sintaxe

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

Uma longest increasing subsequence (LIS), ou subsequência crescente mais longa, seleciona elementos pela sua ordem original. É possível ignorar elementos; a seleção não tem de ser contígua. Para {3, 1, 2, 2, 4}, a subsequência {1, 2, 4} tem o comprimento máximo 3. Ordenar a entrada alteraria o problema, pois perder-se-ia a ordem original.

A distinção strictly increasing versus non-decreasing significa que uma subsequência estritamente crescente exige <, enquanto uma não decrescente permite <=. Valores iguais não prolongam uma LIS. Substituir a[j] < a[i] por a[j] <= a[i] produz um algoritmo para a subsequência não decrescente mais longa; para os dados do exemplo, o seu comprimento é 4.

Seja dp[i] o comprimento da melhor subsequência que termina exatamente em a[i]. Inicialize-o com 1. Para cada j < i que satisfaça a[j] < a[i], considere dp[j] + 1. Calcule os estados da esquerda para a direita e mantenha o resultado mais elevado. Os ciclos aninhados requerem O(n²) tempo e o array dp utiliza O(n) espaço auxiliar.

O exemplo devolve apenas o comprimento. Registar os índices dos predecessores é opcional: se a entrada não estiver vazia, é possível reconstruir uma LIS a partir de a e dp. Comece por selecionar a[i] num índice i em que dp[i] seja máximo. Percorra os índices para trás e selecione a[j] quando se verificarem j < i, a[j] < a[i] e dp[j] + 1 == dp[i]. Após cada seleção, atribua a i o valor de j. Pare quando dp[i] == 1 e inverta a ordem dos elementos selecionados.

Quem chama fornece arrays a e dp que não se sobrepõem e que contêm, cada um, pelo menos n elementos. Para n == 0, a função devolve 0 sem aceder a qualquer dos arrays, pelo que NULL é permitido. Não utiliza alocação dinâmica nem arrays de comprimento variável.

Exemplos

#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

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes