CKTIS / C
Langste stijgende deelrij (LIS)
Een LIS is de langste strikt stijgende deelrij die de invoervolgorde behoudt, zonder dat de elementen aangrenzend hoeven te zijn. Het C-voorbeeld berekent de lengte met dynamisch programmeren in O(n²) tijd en met O(n) extra geheugen.
Versie: 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)Een longest increasing subsequence (LIS), oftewel de langste stijgende deelrij, selecteert elementen in hun oorspronkelijke volgorde. Elementen mogen worden overgeslagen; de selectie hoeft niet aaneengesloten te zijn. Voor {3, 1, 2, 2, 4} heeft de deelrij {1, 2, 4} de maximale lengte 3. De invoer sorteren zou het probleem veranderen doordat de oorspronkelijke volgorde verloren gaat.
Het onderscheid strictly increasing versus non-decreasing betekent dat een strikt stijgende deelrij < vereist, terwijl een niet-dalende deelrij <= toestaat. Gelijke waarden verlengen een LIS niet. Door a[j] < a[i] te vervangen door a[j] <= a[i] ontstaat een algoritme voor de langste niet-dalende deelrij; voor de voorbeeldinvoer is de lengte daarvan 4.
Laat dp[i] de lengte zijn van de beste deelrij die precies eindigt bij a[i]. Stel deze waarde in op 1. Neem voor elke j < i waarvoor a[j] < a[i] geldt, dp[j] + 1 in aanmerking. Bereken de toestanden van links naar rechts en bewaar het grootste resultaat. De geneste lussen kosten O(n²) tijd en de array dp gebruikt O(n) extra geheugen.
Het voorbeeld geeft alleen de lengte terug. Het bijhouden van de indexen van voorgangers is optioneel: bij niet-lege invoer kun je een LIS reconstrueren uit a en dp. Selecteer eerst a[i] op een index i waarvoor dp[i] maximaal is. Doorloop de indexen van rechts naar links en selecteer a[j] als j < i, a[j] < a[i] en dp[j] + 1 == dp[i] gelden. Stel na elke selectie i in op j. Stop zodra dp[i] == 1 en keer de volgorde van de geselecteerde elementen om.
De aanroeper levert niet-overlappende arrays a en dp, die elk ten minste n elementen bevatten. Voor n == 0 geeft de functie 0 terug zonder een van beide arrays te benaderen, dus NULL is toegestaan. De functie gebruikt geen dynamische geheugentoewijzing en geen arrays met variabele lengte.
Voorbeelden
#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;
}
Resultaat
LIS length: 3 Empty length: 0
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.