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.