Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C

Sottosequenza crescente più lunga (LIS)

Una LIS è la sottosequenza strettamente crescente più lunga che conserva l’ordine di input senza richiedere elementi adiacenti. L’esempio in C ne calcola la lunghezza con la programmazione dinamica in tempo O(n²) e usando O(n) spazio ausiliario.

Versione: C23; repository compiler flag, production runtime not attested

Sintassi

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 sottosequenza crescente più lunga, seleziona elementi nel loro ordine originale. È possibile saltare elementi; la selezione non deve essere contigua. Per {3, 1, 2, 2, 4}, la sottosequenza {1, 2, 4} ha lunghezza massima 3. Ordinare l’input cambierebbe il problema, perché si perderebbe l’ordine originale.

La distinzione strictly increasing versus non-decreasing significa che una sottosequenza strettamente crescente richiede <, mentre una non decrescente consente <=. I valori uguali non allungano una LIS. Sostituendo a[j] < a[i] con a[j] <= a[i] si ottiene un algoritmo per la sottosequenza non decrescente più lunga; per i dati dell’esempio, la sua lunghezza è 4.

Sia dp[i] la lunghezza della migliore sottosequenza che termina esattamente in a[i]. Inizializzala a 1. Per ogni j < i che soddisfa a[j] < a[i], considera dp[j] + 1. Calcola gli stati da sinistra a destra e conserva il risultato maggiore. I cicli annidati richiedono tempo O(n²), mentre l’array dp usa O(n) spazio ausiliario.

L’esempio restituisce solo la lunghezza. Memorizzare gli indici dei predecessori è facoltativo: se l’input non è vuoto, puoi ricostruire una LIS a partire da a e dp. Inizia selezionando a[i] in corrispondenza di un indice i per cui dp[i] è massimo. Scorri gli indici all’indietro e seleziona a[j] quando valgono j < i, a[j] < a[i] e dp[j] + 1 == dp[i]. Dopo ogni selezione, assegna a i il valore di j. Fermati quando dp[i] == 1 e inverti l’ordine degli elementi selezionati.

Il chiamante fornisce gli array a e dp, non sovrapposti e ciascuno con almeno n elementi. Per n == 0, la funzione restituisce 0 senza accedere a nessuno dei due array, quindi NULL è consentito. Non usa né allocazione dinamica né array a lunghezza variabile.

Esempi

#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;
}

Risultato

LIS length: 3
Empty length: 0

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti