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.