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.