CKTIS / C
Najdlhšia rastúca podpostupnosť (LIS)
LIS je najdlhšia prísne rastúca podpostupnosť, ktorá zachováva poradie vstupu bez toho, aby prvky museli susediť. Príklad v C počíta jej dĺžku pomocou dynamického programovania v čase O(n²) a s pomocnou pamäťou O(n).
Verzia: C23; repository compiler flag, production runtime not attested
Syntax
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), teda najdlhšia rastúca podpostupnosť, vyberá prvky v ich pôvodnom poradí. Prvky možno vynechať; výber nemusí byť súvislý. Pre {3, 1, 2, 2, 4} má podpostupnosť {1, 2, 4} maximálnu dĺžku 3. Zoradenie vstupu by úlohu zmenilo, pretože by sa stratilo pôvodné poradie.
Rozdiel strictly increasing versus non-decreasing znamená, že prísne rastúca podpostupnosť vyžaduje <, zatiaľ čo neklesajúca povoľuje <=. Rovnaké hodnoty LIS nepredlžujú. Nahradením a[j] < a[i] výrazom a[j] <= a[i] vznikne algoritmus pre najdlhšiu neklesajúcu podpostupnosť; pre vstup z príkladu má dĺžku 4.
Nech dp[i] označuje dĺžku najlepšej podpostupnosti končiacej sa presne na a[i]. Inicializujte ju na 1. Pre každé j < i, pre ktoré platí a[j] < a[i], zvážte dp[j] + 1. Stavy počítajte zľava doprava a uchovajte najväčší výsledok. Vnorené cykly majú časovú zložitosť O(n²) a pole dp používa pomocnú pamäť O(n).
Príklad vracia iba dĺžku. Zaznamenávať indexy predchodcov nie je potrebné: pri neprázdnom vstupe možno LIS obnoviť z polí a a dp. Najprv vyberte a[i] na indexe i, pre ktorý je dp[i] najväčšie. Prechádzajte indexy odzadu a vyberte a[j], ak platí j < i, a[j] < a[i] a dp[j] + 1 == dp[i]. Po každom výbere nastavte i na j. Keď platí dp[i] == 1, skončite a obráťte poradie vybratých prvkov.
Volajúci poskytuje neprekrývajúce sa polia a a dp, každé s aspoň n prvkami. Pre n == 0 funkcia vráti 0 bez prístupu ku ktorémukoľvek z polí, takže NULL je povolené. Nepoužíva dynamickú alokáciu ani polia s premennou dĺžkou.
Prí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ýsledok
LIS length: 3 Empty length: 0
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.