Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Najdłuższy podciąg rosnący (LIS)

LIS to najdłuższy ściśle rosnący podciąg zachowujący kolejność elementów wejścia, ale niekoniecznie ich sąsiedztwo. Przykład w C oblicza jego długość metodą programowania dynamicznego w czasie O(n²), używając O(n) pamięci pomocniczej.

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

Składnia

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

Najdłuższy podciąg rosnący, czyli longest increasing subsequence (LIS), powstaje przez wybranie elementów w ich pierwotnej kolejności. Można pomijać elementy; nie trzeba wybierać spójnego fragmentu. Dla {3, 1, 2, 2, 4} podciąg {1, 2, 4} ma maksymalną długość 3. Sortowanie wejścia zmieniłoby problem, ponieważ zgubiłoby pierwotną kolejność.

Rozróżnienie strictly increasing versus non-decreasing oznacza: ściśle rosnący podciąg wymaga <, a niemalejący dopuszcza <=. Równe wartości nie wydłużają LIS. Zmiana a[j] < a[i] na a[j] <= a[i] daje algorytm dla najdłuższego podciągu niemalejącego; dla danych przykładu jego długość wynosi 4.

Niech dp[i] oznacza długość najlepszego podciągu kończącego się dokładnie na a[i]. Początkowo wynosi 1. Dla każdego j < i spełniającego a[j] < a[i] rozważ dp[j] + 1. Obliczaj stany od lewej do prawej i zachowuj największy wynik. Dwie pętle dają czas O(n²), a tablica dp zajmuje O(n) pamięci pomocniczej.

Przykład zwraca tylko długość. Zapisywanie indeksów poprzedników jest opcjonalne: dla niepustego wejścia podciąg można odtworzyć z a i dp. Zacznij od indeksu i, dla którego dp[i] jest największe, i wybierz a[i]. Idąc wstecz, wybieraj a[j] dla indeksów j < i spełniających a[j] < a[i] oraz dp[j] + 1 == dp[i], po każdym wyborze podstawiając j za i. Zakończ, gdy dp[i] == 1, i odwróć kolejność wybranych elementów.

Wywołujący zapewnia niepokrywające się tablice a i dp, każdą na co najmniej n elementów. Dla n == 0 funkcja zwraca 0 bez odczytu tablic, więc dopuszcza NULL. Nie używa alokacji dynamicznej ani tablic o zmiennej długości.

Przykłady

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

Wynik

LIS length: 3
Empty length: 0

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła