Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C

Nejdelší rostoucí podposloupnost (LIS)

LIS je nejdelší přísně rostoucí podposloupnost, která zachovává pořadí vstupu, aniž by prvky musely sousedit. Příklad v C počítá její délku pomocí dynamického programování v čase O(n²) a s pomocnou pamětí O(n).

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

Syntaxe

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), tedy nejdelší rostoucí podposloupnost, vybírá prvky v jejich původním pořadí. Prvky lze vynechávat; výběr nemusí být souvislý. Pro {3, 1, 2, 2, 4} má podposloupnost {1, 2, 4} maximální délku 3. Seřazení vstupu by úlohu změnilo, protože by se ztratilo původní pořadí.

Rozdíl strictly increasing versus non-decreasing znamená, že přísně rostoucí podposloupnost vyžaduje <, zatímco neklesající dovoluje <=. Stejné hodnoty LIS neprodlužují. Nahrazením a[j] < a[i] výrazem a[j] <= a[i] vznikne algoritmus pro nejdelší neklesající podposloupnost; pro vstup z příkladu má délku 4.

Nechť dp[i] označuje délku nejlepší podposloupnosti končící přesně na a[i]. Inicializujte ji na 1. Pro každé j < i, pro které platí a[j] < a[i], zvažte dp[j] + 1. Stavy počítejte zleva doprava a uchovávejte největší výsledek. Vnořené cykly mají časovou složitost O(n²) a pole dp používá pomocnou paměť O(n).

Příklad vrací pouze délku. Ukládání indexů předchůdců není nutné: pro neprázdný vstup lze LIS obnovit z polí a a dp. Nejprve vyberte a[i] na indexu i, pro který je dp[i] největší. Procházejte indexy zpět a vyberte a[j], pokud platí j < i, a[j] < a[i] a dp[j] + 1 == dp[i]. Po každém výběru nastavte i na j. Jakmile platí dp[i] == 1, skončete a obraťte pořadí vybraných prvků.

Volající poskytuje nepřekrývající se pole a a dp, každé s alespoň n prvky. Pro n == 0 funkce vrátí 0, aniž by přistupovala k některému z polí, takže NULL je povoleno. Nepoužívá dynamickou alokaci ani pole s proměnnou délkou.

Pří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ýsledek

LIS length: 3
Empty length: 0

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje