Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C

Najdlhšia rastúca podpostupnosť (LIS)

LIS je najdlhšia prísne rastúca podpostupnosť, ktorá zachováva poradie vstupu bez toho, aby prvky museli susediť. Príklad v C počíta jej dĺžku pomocou dynamického programovania v čase O(n²) a s pomocnou pamäťou O(n).

Verzia: 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)

Longest increasing subsequence (LIS), teda najdlhšia rastúca podpostupnosť, vyberá prvky v ich pôvodnom poradí. Prvky možno vynechať; výber nemusí byť súvislý. Pre {3, 1, 2, 2, 4} má podpostupnosť {1, 2, 4} maximálnu dĺžku 3. Zoradenie vstupu by úlohu zmenilo, pretože by sa stratilo pôvodné poradie.

Rozdiel strictly increasing versus non-decreasing znamená, že prísne rastúca podpostupnosť vyžaduje <, zatiaľ čo neklesajúca povoľuje <=. Rovnaké hodnoty LIS nepredlžujú. Nahradením a[j] < a[i] výrazom a[j] <= a[i] vznikne algoritmus pre najdlhšiu neklesajúcu podpostupnosť; pre vstup z príkladu má dĺžku 4.

Nech dp[i] označuje dĺžku najlepšej podpostupnosti končiacej sa presne na a[i]. Inicializujte ju na 1. Pre každé j < i, pre ktoré platí a[j] < a[i], zvážte dp[j] + 1. Stavy počítajte zľava doprava a uchovajte najväčší výsledok. Vnorené cykly majú časovú zložitosť O(n²) a pole dp používa pomocnú pamäť O(n).

Príklad vracia iba dĺžku. Zaznamenávať indexy predchodcov nie je potrebné: pri neprázdnom vstupe možno LIS obnoviť z polí a a dp. Najprv vyberte a[i] na indexe i, pre ktorý je dp[i] najväčšie. Prechádzajte indexy odzadu a vyberte a[j], ak platí j < i, a[j] < a[i] a dp[j] + 1 == dp[i]. Po každom výbere nastavte i na j. Keď platí dp[i] == 1, skončite a obráťte poradie vybratých prvkov.

Volajúci poskytuje neprekrývajúce sa polia a a dp, každé s aspoň n prvkami. Pre n == 0 funkcia vráti 0 bez prístupu ku ktorémukoľvek z polí, takže NULL je povolené. Nepoužíva dynamickú alokáciu ani polia s premennou dĺžkou.

Príklady

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

Výsledok

LIS length: 3
Empty length: 0

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje