WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

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.

Quellen