Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C

Najdulji rastući podniz (LIS)

LIS je najdulji strogo rastući podniz koji čuva redoslijed ulaza, bez uvjeta da elementi budu susjedni. Primjer u C-u računa njegovu duljinu dinamičkim programiranjem u vremenu O(n²) i uz O(n) pomoćne memorije.

Verzija: 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), odnosno najdulji rastući podniz, odabire elemente prema njihovu izvornom redoslijedu. Elemente je moguće preskočiti; odabir ne mora biti neprekinut. Za {3, 1, 2, 2, 4} podniz {1, 2, 4} ima najveću duljinu 3. Sortiranje ulaza promijenilo bi problem jer bi se izgubio izvorni redoslijed.

Razlika strictly increasing versus non-decreasing znači da strogo rastući podniz zahtijeva <, dok neopadajući dopušta <=. Jednake vrijednosti ne produljuju LIS. Zamjenom a[j] < a[i] s a[j] <= a[i] dobiva se algoritam za najdulji neopadajući podniz; njegova duljina za ulaz iz primjera iznosi 4.

Neka je dp[i] duljina najboljeg podniza koji završava točno na a[i]. Postavite je na 1. Za svaki j < i za koji vrijedi a[j] < a[i], razmotrite dp[j] + 1. Stanja računajte slijeva nadesno i zadržite najveći rezultat. Ugniježđene petlje zahtijevaju vrijeme O(n²), a polje dp koristi O(n) pomoćne memorije.

Primjer vraća samo duljinu. Bilježenje indeksa prethodnika nije obvezno: ako ulaz nije prazan, LIS se može rekonstruirati iz polja a i dp. Najprije odaberite a[i] na indeksu i za koji je dp[i] najveći. Prolazite indeksima unatrag i odaberite a[j] kad vrijede j < i, a[j] < a[i] i dp[j] + 1 == dp[i]. Nakon svakog odabira postavite i na j. Zaustavite se kad vrijedi dp[i] == 1 i obrnite redoslijed odabranih elemenata.

Pozivatelj daje nepoklapajuća polja a i dp, od kojih svako sadrži najmanje n elemenata. Za n == 0 funkcija vraća 0 bez pristupa bilo kojem polju, pa je NULL dopušten. Ne koristi dinamičku alokaciju ni polja promjenjive duljine.

Primjeri

#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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori