CKTIS / C
Längste aufsteigende Teilfolge (LIS)
Eine LIS ist die längste streng aufsteigende Teilfolge, die die Reihenfolge der Eingabe beibehält, ohne dass die Elemente benachbart sein müssen. Das C-Beispiel berechnet ihre Länge mit dynamischer Programmierung in O(n²) Zeit und O(n) zusätzlichem Speicher.
Version: 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)Eine longest increasing subsequence (LIS), also eine längste aufsteigende Teilfolge, wählt Elemente in ihrer ursprünglichen Reihenfolge aus. Elemente dürfen ausgelassen werden; die Auswahl muss nicht zusammenhängend sein. Für {3, 1, 2, 2, 4} hat die Teilfolge {1, 2, 4} die maximale Länge 3. Das Sortieren der Eingabe würde das Problem verändern, weil dabei die ursprüngliche Reihenfolge verloren ginge.
Der Unterschied zwischen strictly increasing versus non-decreasing besteht darin, dass eine streng aufsteigende Teilfolge < erfordert, während eine nicht fallende Teilfolge <= zulässt. Gleiche Werte verlängern eine LIS nicht. Ersetzt man a[j] < a[i] durch a[j] <= a[i], erhält man einen Algorithmus für die längste nicht fallende Teilfolge; für die Beispieldaten beträgt ihre Länge 4.
Sei dp[i] die Länge der besten Teilfolge, die genau bei a[i] endet. Initialisiere den Wert mit 1. Für jedes j < i, für das a[j] < a[i] gilt, wird dp[j] + 1 berücksichtigt. Berechne die Zustände von links nach rechts und behalte das größte Ergebnis. Die verschachtelten Schleifen benötigen O(n²) Zeit; das Array dp benötigt O(n) zusätzlichen Speicher.
Das Beispiel gibt nur die Länge zurück. Das Speichern von Vorgängerindizes ist optional: Bei nicht leerer Eingabe lässt sich eine LIS aus a und dp rekonstruieren. Wähle zuerst a[i] an einem Index i, an dem dp[i] maximal ist. Gehe rückwärts durch die Indizes und wähle a[j], wenn j < i, a[j] < a[i] und dp[j] + 1 == dp[i] gelten. Setze nach jeder Auswahl i auf j. Beende die Suche, sobald dp[i] == 1 gilt, und kehre die Reihenfolge der ausgewählten Elemente um.
Der Aufrufer stellt nicht überlappende Arrays a und dp bereit, die jeweils mindestens n Elemente enthalten. Für n == 0 gibt die Funktion 0 zurück, ohne eines der Arrays zu lesen; daher ist NULL zulässig. Es werden weder dynamische Speicherzuweisung noch Arrays variabler Länge verwendet.
Beispiele
#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;
}
Ergebnis
LIS length: 3 Empty length: 0
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.