KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C

Langste stijgende deelrij (LIS)

Een LIS is de langste strikt stijgende deelrij die de invoervolgorde behoudt, zonder dat de elementen aangrenzend hoeven te zijn. Het C-voorbeeld berekent de lengte met dynamisch programmeren in O(n²) tijd en met O(n) extra geheugen.

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

Syntax

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

Een longest increasing subsequence (LIS), oftewel de langste stijgende deelrij, selecteert elementen in hun oorspronkelijke volgorde. Elementen mogen worden overgeslagen; de selectie hoeft niet aaneengesloten te zijn. Voor {3, 1, 2, 2, 4} heeft de deelrij {1, 2, 4} de maximale lengte 3. De invoer sorteren zou het probleem veranderen doordat de oorspronkelijke volgorde verloren gaat.

Het onderscheid strictly increasing versus non-decreasing betekent dat een strikt stijgende deelrij < vereist, terwijl een niet-dalende deelrij <= toestaat. Gelijke waarden verlengen een LIS niet. Door a[j] < a[i] te vervangen door a[j] <= a[i] ontstaat een algoritme voor de langste niet-dalende deelrij; voor de voorbeeldinvoer is de lengte daarvan 4.

Laat dp[i] de lengte zijn van de beste deelrij die precies eindigt bij a[i]. Stel deze waarde in op 1. Neem voor elke j < i waarvoor a[j] < a[i] geldt, dp[j] + 1 in aanmerking. Bereken de toestanden van links naar rechts en bewaar het grootste resultaat. De geneste lussen kosten O(n²) tijd en de array dp gebruikt O(n) extra geheugen.

Het voorbeeld geeft alleen de lengte terug. Het bijhouden van de indexen van voorgangers is optioneel: bij niet-lege invoer kun je een LIS reconstrueren uit a en dp. Selecteer eerst a[i] op een index i waarvoor dp[i] maximaal is. Doorloop de indexen van rechts naar links en selecteer a[j] als j < i, a[j] < a[i] en dp[j] + 1 == dp[i] gelden. Stel na elke selectie i in op j. Stop zodra dp[i] == 1 en keer de volgorde van de geselecteerde elementen om.

De aanroeper levert niet-overlappende arrays a en dp, die elk ten minste n elementen bevatten. Voor n == 0 geeft de functie 0 terug zonder een van beide arrays te benaderen, dus NULL is toegestaan. De functie gebruikt geen dynamische geheugentoewijzing en geen arrays met variabele lengte.

Voorbeelden

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

Resultaat

LIS length: 3
Empty length: 0

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen