Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C

Plus longue sous-séquence croissante (LIS)

Une LIS est la plus longue sous-séquence strictement croissante qui conserve l’ordre d’entrée sans exiger que les éléments soient adjacents. L’exemple en C calcule sa longueur par programmation dynamique en O(n²) temps et avec O(n) mémoire auxiliaire.

Version : C23; repository compiler flag, production runtime not attested

Syntaxe

dp[i] = max({1} union {dp[j] + 1 | 0 <= j < i and a[j] < a[i]}); LIS length = n == 0 ? 0 : max(dp)

Une longest increasing subsequence (LIS), ou plus longue sous-séquence croissante, sélectionne des éléments dans leur ordre d’origine. Il est possible d’ignorer des éléments ; la sélection n’a pas besoin d’être contiguë. Pour {3, 1, 2, 2, 4}, la sous-séquence {1, 2, 4} a la longueur maximale 3. Trier l’entrée modifierait le problème, car cela ferait perdre l’ordre d’origine.

La distinction strictly increasing versus non-decreasing signifie qu’une sous-séquence strictement croissante exige <, tandis qu’une sous-séquence non décroissante autorise <=. Des valeurs égales ne prolongent pas une LIS. Remplacer a[j] < a[i] par a[j] <= a[i] donne un algorithme pour la plus longue sous-séquence non décroissante ; sa longueur pour les données de l’exemple est 4.

Soit dp[i] la longueur de la meilleure sous-séquence se terminant exactement en a[i]. Initialisez cette valeur à 1. Pour chaque j < i tel que a[j] < a[i], considérez dp[j] + 1. Calculez les états de gauche à droite et conservez le résultat le plus grand. Les boucles imbriquées prennent O(n²) temps, et le tableau dp utilise O(n) mémoire auxiliaire.

L’exemple renvoie uniquement la longueur. Il n’est pas nécessaire de mémoriser les indices des prédécesseurs : si l’entrée n’est pas vide, on peut reconstruire une LIS à partir de a et de dp. Sélectionnez d’abord a[i] à un indice i où dp[i] est maximal. Parcourez les indices en sens inverse et sélectionnez a[j] lorsque j < i, a[j] < a[i] et dp[j] + 1 == dp[i]. Après chaque sélection, remplacez i par j. Arrêtez-vous lorsque dp[i] == 1, puis inversez l’ordre des éléments sélectionnés.

L’appelant fournit des tableaux a et dp sans chevauchement, contenant chacun au moins n éléments. Pour n == 0, la fonction renvoie 0 sans accéder à l’un ou l’autre tableau ; NULL est donc autorisé. Elle n’utilise ni allocation dynamique ni tableaux de longueur variable.

Exemples

#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;
}

Résultat

LIS length: 3
Empty length: 0

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources