On nous donne un tableau de $n$ nombres : $a$.La tâche est de trouver la plus longue sous-séquence, strictement croissante, dans $a$.

Formellement, nous cherchons la plus longue séquence d’indices $i_1, \dots i_k$ telle que$$i_1 < i_2 < \dots < i_k,\a < a < \dots < a$

Dans cet article, nous discutons de plusieurs algorithmes pour résoudre cette tâche.Nous discuterons également d’autres problèmes, qui peuvent être réduits à ce problème.

Solution en $O(n^2)$ avec la programmation dynamique

La programmation dynamique est une technique très générale qui permet de résoudre une énorme classe de problèmes.Ici, nous appliquons la technique pour notre tâche spécifique.

Dans un premier temps, nous allons rechercher uniquement la longueur de la plus longue sous-séquence croissante, et seulement plus tard, nous apprendrons à rétablir la sous-séquence elle-même.

Trouver la longueur

Pour accomplir cette tâche, nous définissons un tableau $d$, où $d$ est la longueur de la plus longue sous-séquence croissante qui se termine par l’élément à l’indice $i$.Nous allons calculer ce tableau progressivement : d’abord $d$, puis $d$, et ainsi de suite.Après le calcul de ce tableau, la réponse au problème sera la valeur maximale dans le tableau $d$.

Disons donc que l’indice courant est $i$.C’est-à-dire que nous voulons calculer la valeur $d$ et que toutes les valeurs précédentes $d, \dots, d$ sont déjà connues.Il y a alors deux options :

• $d = 1$ : la sous-séquence requise est constituée uniquement de l’élément $a$.
• $d > 1$ : alors dans la sous-séquence requise se trouve un autre nombre avant le nombre $a$.Concentrons-nous sur ce nombre :ce peut être n’importe quel élément $a$ avec $j = 0 \dots i-1$ et $a < a$.De cette façon, nous pouvons calculer $d$ en utilisant la formule suivante:Si nous fixons l’indice $j$, alors la plus longue sous-séquence croissante se terminant par les deux éléments $a$ et $a$ a la longueur $d + 1$.Toutes ces valeurs $d$ sont déjà connues, donc nous pouvons directement calculer $d$ avec:$$d = \max_{\substack{j = 0 \dots i-1 \\\a < a}} \left(d + 1\right)$$

Si on combine ces deux cas, on obtient la réponse finale pour $d$:

$d = \max\left(1, \max_{\substack{j = 0 \dots i-1 \\\\\\\\a < a} \left(d + 1\right)\right)$$

Implémentation

Voici une implémentation de l’algorithme décrit ci-dessus, qui calcule la longueur de la plus longue sous-séquence croissante.

int lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

Restauration de la sous-séquence

Jusqu’ici, nous avons seulement appris comment trouver la longueur de la sous-séquence, mais pas comment trouver la sous-séquence elle-même.

Pour pouvoir rétablir la sous-séquence, nous générons un tableau auxiliaire supplémentaire $p$ que nous calculerons à côté du tableau $d$.$p$ sera l’indice $j$ de l’avant-dernier élément de la plus longue sous-séquence croissante se terminant par $i$.En d’autres termes, l’indice $p$ est le même indice $j$ auquel la valeur la plus élevée $d$ a été obtenue.Ce tableau auxiliaire $p$ pointe en quelque sorte vers les ancêtres.

Puis pour dériver la sous-séquence, il suffit de commencer à l’indice $i$ avec le $d$ maximal, et de suivre les ancêtres jusqu’à ce que nous ayons déduit la sous-séquence entière, c’est-à-dire jusqu’à ce que nous atteignions l’élément avec $d = 1$.

Mise en œuvre de la restauration

Nous allons modifier un peu le code des sections précédentes.Nous allons calculer le tableau $p$ à côté de $d$, et ensuite calculer la sous-séquence.

Pour des raisons de commodité, nous assignons initialement aux ancêtres avec $p = -1$.Pour les éléments avec $d = 1$, la valeur des ancêtres restera $-1$, ce qui sera légèrement plus pratique pour restaurer la sous-séquence.

vector<int> lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1), p(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

Mode alternatif de restauration de la sous-séquence

Il est également possible de restaurer la sous-séquence sans le tableau auxiliaire $p$.Nous pouvons simplement recalculer la valeur actuelle de $d$ et aussi voir comment le maximum a été atteint.

Cette méthode conduit à un code légèrement plus long, mais en retour nous économisons un peu de mémoire.

Solution en $O(n \log n)$ avec programmation dynamique et recherche binaire

Afin d’obtenir une solution plus rapide pour le problème, nous construisons une solution de programmation dynamique différente qui s’exécute en $O(n^2)$, puis nous l’améliorons par la suite en $O(n \log n)$.

Nous allons utiliser le tableau de programmation dynamique $d$.Cette fois-ci, $d$ sera l’élément auquel se termine une sous-séquence de longueur $i$.S’il existe plusieurs de ces séquences, alors nous prenons celle qui se termine par le plus petit élément.

Initialement, nous supposons $d = -\infty$ et pour tous les autres éléments $d = \infty$.

Nous allons à nouveau traiter progressivement les nombres, d’abord $a$, puis $a$, etc, et à chaque étape maintenir le tableau $d$ de façon à ce qu’il soit à jour.

Après avoir traité tous les éléments de $a$, la longueur de la sous-séquence désirée est le plus grand $l$ avec $d < \infty$.

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Nous faisons maintenant deux observations importantes.

Le tableau $d$ sera toujours trié : $d \le d$ pour tout $i = 1 \dots n$.Et aussi l’élément $a$ ne mettra à jour qu’au plus une valeur $d$.

On peut donc trouver cet élément dans le tableau $d$ en utilisant la recherche binaire en $O(\log n)$.En fait, nous cherchons simplement dans le tableau $d$ le premier nombre qui est strictement supérieur à $a$, et nous essayons de mettre à jour cet élément de la même manière que l’implémentation ci-dessus.

Implémentation

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { int j = upper_bound(d.begin(), d.end(), a) - d.begin(); if (d < a && a < d) d = a; } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Restauration de la sous-séquence

Il est également possible de restaurer la sous-séquence en utilisant cette approche.Cette fois, nous devons maintenir deux tableaux auxiliaires.L’un qui nous indique l’indice des éléments de $d$.Et à nouveau, nous devons créer un tableau d' »ancêtres » $p$.$p$ sera l’indice de l’élément précédent pour la sous-séquence optimale se terminant par l’élément $i$.

Il est facile de maintenir ces deux tableaux au cours de l’itération sur le tableau $a$ parallèlement aux calculs de $d$.Et à la fin, il n’est pas difficile de rétablir la sous-séquence désirée en utilisant ces tableaux.

Solution en $O(n \log n)$ avec des structures de données

Au lieu de la méthode ci-dessus pour calculer la plus longue sous-séquence croissante en $O(n \log n)$, nous pouvons aussi résoudre le problème d’une manière différente : en utilisant quelques structures de données simples.

Retournons à la première méthode.Rappelons que $d$ est la valeur $d + 1$ avec $j < i$ et $a < a$.

Donc si nous définissons un tableau supplémentaire $t$ tel que$t] = d,$$alors le problème de calculer la valeur $d$ est équivalent à trouver la valeur maximale d’un préfixe du tableau $t$:$$d = \max\left(t – 1] + 1\right)$$

Le problème de trouver le maximum d’un préfixe d’un tableau (qui change) est un problème standard qui peut être résolu par de nombreuses structures de données différentes. Par exemple, nous pouvons utiliser un arbre de segment ou un arbre de Fenwick.

Cette méthode a évidemment des défauts : en termes de longueur et de complexité de l’implémentation, cette approche sera pire que la méthode utilisant la recherche binaire.De plus, si les nombres d’entrée $a$ sont particulièrement grands, alors nous devrions utiliser quelques astuces, comme la compression des nombres (c’est-à-dire les renuméroter de $0$ à $n-1$), ou utiliser un arbre de segment implicite (générer seulement les branches de l’arbre qui sont importantes).Sinon, la consommation de mémoire sera trop élevée.

D’un autre côté, cette méthode a aussi quelques avantages:avec cette méthode, vous n’avez pas à penser à des propriétés délicates dans la solution de programmation dynamique.Et cette approche nous permet de généraliser le problème très facilement (voir ci-dessous).

Tâches connexes

Voici plusieurs problèmes qui sont étroitement liés au problème de trouver la plus longue sous-séquence croissante.

La plus longue sous-séquence non décroissante

C’est en fait presque le même problème.Seulement maintenant il est permis d’utiliser des nombres identiques dans la sous-séquence.

La solution est essentiellement aussi presque la même.Il suffit de changer les signes d’inégalité, et d’apporter une légère modification à la recherche binaire.

Nombre de sous-séquences croissantes les plus longues

On peut utiliser la première méthode discutée, soit la version $O(n^2)$, soit la version utilisant des structures de données.Il suffit de stocker en plus de combien de façons on peut obtenir des sous-séquences croissantes les plus longues se terminant par les valeurs $d$.

Le nombre de façons de former une sous-séquence croissante la plus longue se terminant par $a$ est la somme de toutes les façons pour toutes les sous-séquences croissantes les plus longues se terminant par $j$ où $d$ est maximal.Il peut y avoir plusieurs de ces $j$, donc nous devons les additionner toutes.

En utilisant un arbre de segmentation, cette approche peut également être implémentée en $O(n \log n)$.

Il n’est pas possible d’utiliser l’approche de recherche binaire pour cette tâche.

Plus petit nombre de sous-séquences non croissantes couvrant une séquence

Pour un tableau donné avec $n$ chiffres $a$, nous devons colorier les chiffres dans le plus petit nombre de couleurs, de sorte que chaque couleur forme une sous-séquence non croissante.

Pour le résoudre, on remarque que le nombre minimal de couleurs requises est égal à la longueur de la plus longue sous-séquence croissante.

Preuve : Il faut prouver la dualité de ces deux problèmes.

Dénotons par $x$ la longueur de la plus longue sous-séquence croissante et par $y$ le plus petit nombre de sous-séquences non croissantes qui forment une couverture.Nous devons prouver que $x = y$.

Il est clair que $y < x$ n’est pas possible, car si nous avons $x$ éléments strictement croissants, alors aucun ne peut faire partie de la même sous-séquence non croissante.Par conséquent, nous avons $y \ge x$.

Nous montrons maintenant que $y > x$ n’est pas possible par contradiction.Supposons que $y > x$.Nous considérons alors tout ensemble optimal de $y$ sous-séquences non croissantes.Nous transformons cet ensemble de la manière suivante : tant qu’il existe deux telles sous-séquences telles que la première commence avant la seconde sous-séquence, et que la première séquence commence par un nombre supérieur ou égal à la seconde, alors nous décrochons ce nombre de départ et le rattachons au début de la seconde.Après un nombre fini d’étapes, nous avons $y$ sous-séquences, et leurs numéros de départ formeront une sous-séquence croissante de longueur $y$.Comme nous avons supposé que $y > x$, nous sommes arrivés à une contradiction.

Il s’ensuit donc que $y = x$.

Restauration des séquences:La partition souhaitée de la séquence en sous-séquences peut être faite de manière avide.C’est-à-dire aller de gauche à droite et attribuer le numéro actuel ou cette sous-séquence se terminant par le numéro minimal qui est supérieur ou égal au numéro actuel.

Problèmes pratiques

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Touriste
• Codeforces – LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – « Nord-Est »

.