CKTIS / C
Najdaljše naraščajoče podzaporedje (LIS)
LIS je najdaljše strogo naraščajoče podzaporedje, ki ohranja vrstni red vhodnih podatkov, ne da bi morali biti elementi sosednji. Primer v C izračuna njegovo dolžino z dinamičnim programiranjem v času O(n²) in z O(n) pomožnega pomnilnika.
Različica: 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), torej najdaljše naraščajoče podzaporedje, izbira elemente v njihovem prvotnem vrstnem redu. Elemente je mogoče izpustiti; izbira ni nujno strnjena. Za {3, 1, 2, 2, 4} ima podzaporedje {1, 2, 4} največjo dolžino 3. Urejanje vhodnih podatkov bi spremenilo problem, saj bi se izgubil prvotni vrstni red.
Razlika strictly increasing versus non-decreasing pomeni, da strogo naraščajoče podzaporedje zahteva <, medtem ko nepadajoče dovoljuje <=. Enake vrednosti LIS ne podaljšajo. Če a[j] < a[i] zamenjamo z a[j] <= a[i], dobimo algoritem za najdaljše nepadajoče podzaporedje; za vhodne podatke iz primera je njegova dolžina 4.
Naj bo dp[i] dolžina najboljšega podzaporedja, ki se konča natanko pri a[i]. Nastavite jo na 1. Za vsak j < i, za katerega velja a[j] < a[i], upoštevajte dp[j] + 1. Stanja izračunavajte od leve proti desni in ohranite največji rezultat. Ugnezdeni zanki zahtevata čas O(n²), polje dp pa uporablja O(n) pomožnega pomnilnika.
Primer vrne samo dolžino. Indeksov predhodnikov ni treba shranjevati: pri nepraznem vhodu lahko LIS rekonstruirate iz polj a in dp. Najprej izberite a[i] pri indeksu i, za katerega je dp[i] največji. Pomikajte se po indeksih nazaj in izberite a[j], ko veljajo j < i, a[j] < a[i] in dp[j] + 1 == dp[i]. Po vsaki izbiri nastavite i na j. Ustavite se, ko velja dp[i] == 1, in obrnite vrstni red izbranih elementov.
Klicatelj zagotovi polji a in dp, ki se v pomnilniku ne prekrivata in imata vsako vsaj n elementov. Za n == 0 funkcija vrne 0, ne da bi dostopala do katerega koli polja, zato je NULL dovoljen. Ne uporablja dinamičnega dodeljevanja pomnilnika ali polj spremenljive dolžine.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.