Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C

Najdaljše naraščajoče podzaporedje (LIS)

LIS je najdaljše strogo naraščajoče podzaporedje, ki ohranja vrstni red vhodnih podatkov, ne da bi morali biti elementi sosednji. Primer v C izračuna njegovo dolžino z dinamičnim programiranjem v času O(n²) in z O(n) pomožnega pomnilnika.

Različica: C23; repository compiler flag, production runtime not attested

Sintaksa

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

Longest increasing subsequence (LIS), torej najdaljše naraščajoče podzaporedje, izbira elemente v njihovem prvotnem vrstnem redu. Elemente je mogoče izpustiti; izbira ni nujno strnjena. Za {3, 1, 2, 2, 4} ima podzaporedje {1, 2, 4} največjo dolžino 3. Urejanje vhodnih podatkov bi spremenilo problem, saj bi se izgubil prvotni vrstni red.

Razlika strictly increasing versus non-decreasing pomeni, da strogo naraščajoče podzaporedje zahteva <, medtem ko nepadajoče dovoljuje <=. Enake vrednosti LIS ne podaljšajo. Če a[j] < a[i] zamenjamo z a[j] <= a[i], dobimo algoritem za najdaljše nepadajoče podzaporedje; za vhodne podatke iz primera je njegova dolžina 4.

Naj bo dp[i] dolžina najboljšega podzaporedja, ki se konča natanko pri a[i]. Nastavite jo na 1. Za vsak j < i, za katerega velja a[j] < a[i], upoštevajte dp[j] + 1. Stanja izračunavajte od leve proti desni in ohranite največji rezultat. Ugnezdeni zanki zahtevata čas O(n²), polje dp pa uporablja O(n) pomožnega pomnilnika.

Primer vrne samo dolžino. Indeksov predhodnikov ni treba shranjevati: pri nepraznem vhodu lahko LIS rekonstruirate iz polj a in dp. Najprej izberite a[i] pri indeksu i, za katerega je dp[i] največji. Pomikajte se po indeksih nazaj in izberite a[j], ko veljajo j < i, a[j] < a[i] in dp[j] + 1 == dp[i]. Po vsaki izbiri nastavite i na j. Ustavite se, ko velja dp[i] == 1, in obrnite vrstni red izbranih elementov.

Klicatelj zagotovi polji a in dp, ki se v pomnilniku ne prekrivata in imata vsako vsaj n elementov. Za n == 0 funkcija vrne 0, ne da bi dostopala do katerega koli polja, zato je NULL dovoljen. Ne uporablja dinamičnega dodeljevanja pomnilnika ali polj spremenljive dolžine.

Primeri

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

Rezultat

LIS length: 3
Empty length: 0

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri