Devinette : sous-suite croissante ou décroissante

Énoncé

Soit une suite de n^2+1 nombres distincts.

Montrer qu’elle contient toujours :

soit une sous-suite strictement croissante d’au moins n+1 termes ;
soit une sous-suite strictement décroissante d’au moins n+1 termes.

Une sous-suite est obtenue en conservant certains termes dans leur ordre d’origine, sans exiger qu’ils soient consécutifs.

Exemple :

(8,3,6,1,5,7)

contient la sous-suite croissante

(3,6,7)

et la sous-suite décroissante

(8,6,5).

Indice

Pour chaque terme a_k, associer deux nombres :

c_k : longueur de la plus longue sous-suite croissante qui se termine en a_k ;
d_k : longueur de la plus longue sous-suite décroissante qui se termine en a_k.

Supposer qu’aucune sous-suite croissante ou décroissante n’a plus de n termes.

Chaque terme reçoit alors un couple

(c_k,d_k)\in\{1,\ldots,n\}^2.

Il n’existe que n^2 couples possibles.

Il reste à comprendre pourquoi deux termes placés à des indices différents ne peuvent pas recevoir le même couple.

Solution numérique : principe des tiroirs

Considérons une suite

a_1,a_2,\ldots,a_{n^2+1}

de nombres distincts.

Pour chaque indice k, définissons :

c_k=\text{longueur maximale d’une sous-suite croissante terminant en }a_k,

d_k=\text{longueur maximale d’une sous-suite décroissante terminant en }a_k.

Supposons, par contradiction, qu’il n’existe :

aucune sous-suite croissante de longueur n+1 ;
aucune sous-suite décroissante de longueur n+1.

On a alors, pour tout k,

1\leq c_k\leq n \qquad\text{et}\qquad 1\leq d_k\leq n.

Chaque terme reçoit donc un couple parmi les n^2 couples de la grille

\{1,\ldots,n\}\times\{1,\ldots,n\}.

Montrons que ces couples sont tous distincts.

Prenons deux indices i<j.

Comme les valeurs sont distinctes, il existe deux cas.

Premier cas : a_i<a_j

Une sous-suite croissante maximale terminant en a_i, de longueur c_i, peut être prolongée par a_j.

Donc

c_j\geq c_i+1.

En particulier,

c_j\neq c_i.

Les couples (c_i,d_i) et (c_j,d_j) sont différents.

Second cas : a_i>a_j

Une sous-suite décroissante maximale terminant en a_i, de longueur d_i, peut être prolongée par a_j.

Donc

d_j\geq d_i+1.

En particulier,

d_j\neq d_i.

Les couples sont encore différents.

Ainsi, les n^2+1 termes reçoivent n^2+1 couples distincts, alors qu’il n’existe que n^2 couples possibles.

Contradiction.

Il existe donc nécessairement une sous-suite croissante ou décroissante d’au moins n+1 termes.

Ce résultat est un cas du théorème d’Erdős–Szekeres.

Solution géométrique

Représentons chaque terme a_i par un point du plan :

P_i=(i,a_i).

L’axe horizontal représente l’indice dans la suite. Les points sont donc toujours parcourus de gauche à droite.

Une sous-suite croissante correspond à une chaîne de points allant vers le nord-est :

i_1<i_2<\cdots<i_r \quad\text{et}\quad a_{i_1}<a_{i_2}<\cdots<a_{i_r}.

Une sous-suite décroissante correspond à une chaîne allant vers le sud-est :

i_1<i_2<\cdots<i_r \quad\text{et}\quad a_{i_1}>a_{i_2}>\cdots>a_{i_r}.

À chaque point P_i, associons l’étiquette

(c_i,d_i),

où :

c_i est la longueur maximale d’une chaîne nord-est terminant en P_i ;
d_i est la longueur maximale d’une chaîne sud-est terminant en P_i.

Prenons deux points P_i et P_j avec i<j. Le point P_j se trouve à droite de P_i.

Comme les valeurs sont distinctes :

soit P_j est au-dessus de P_i, et une chaîne nord-est terminant en P_i se prolonge jusqu’à P_j ;
soit P_j est en dessous de P_i, et une chaîne sud-est terminant en P_i se prolonge jusqu’à P_j.

Deux points ne peuvent donc jamais avoir la même étiquette.

Si toutes les chaînes croissantes et décroissantes avaient une longueur au plus n, les étiquettes seraient toutes contenues dans une grille n\times n.

Cette grille ne contient que n^2 positions, mais il faut y placer n^2+1 étiquettes distinctes.

C’est impossible.

Recherche algorithmique d’une sous-suite

On considère maintenant une suite de longueur générale N :

a_0,a_1,\ldots,a_{N-1}.

Le problème informatique consiste à trouver effectivement une plus longue sous-suite croissante, souvent appelée LIS pour Longest Increasing Subsequence.

La version décroissante s’obtient en inversant les comparaisons, ou en appliquant l’algorithme croissant aux valeurs opposées -a_i.

Algorithme 1 : programmation dynamique en O(N^2)

Idée

Pour chaque position i, on calcule la longueur de la plus longue sous-suite croissante qui se termine exactement en a_i.

Définissons :

L[i] = 1+\max\{L[j]\mid j<i\text{ et }a_j<a_i\}.

S’il n’existe aucun indice j convenable, on pose :

L[i]=1.

Pour reconstruire la sous-suite, on conserve aussi :

P[i]=\text{indice du prédécesseur choisi avant }a_i.

Pseudo-code

fonction lis_dynamique(a):
    N = longueur(a)

    L = tableau de N cases initialisées à 1
    P = tableau de N cases initialisées à -1

    pour i de 0 à N - 1:
        pour j de 0 à i - 1:
            si a[j] < a[i] et L[j] + 1 > L[i]:
                L[i] = L[j] + 1
                P[i] = j

    fin = indice où L est maximal

    résultat = liste vide
    tant que fin != -1:
        ajouter a[fin] à résultat
        fin = P[fin]

    renverser résultat
    retourner résultat

Exemple

Pour

(4,2,7,3,8),

on obtient par exemple :

indice : 0  1  2  3  4
valeur : 4  2  7  3  8
L      : 1  1  2  2  3
P      : -  -  0  1  2

En partant de l’indice 4, on remonte :

8 <- 7 <- 4

Après inversion :

(4,7,8).

Une autre sous-suite optimale peut exister, selon la manière de départager les choix.

Complexité temporelle

La boucle extérieure parcourt N positions.

Pour chaque position i, la boucle intérieure examine les i positions précédentes.

Le nombre total de comparaisons est :

0+1+2+\cdots+(N-1) = \frac{N(N-1)}{2}.

Donc :

T(N)=O(N^2).

La reconstruction prend au plus O(N), ce qui ne change pas la complexité totale.

Complexité mémoire

Les tableaux L et P contiennent chacun N éléments.

Donc :

M(N)=O(N).

Si seule la longueur est demandée, le tableau des prédécesseurs peut être supprimé, mais le tableau L reste nécessaire dans cette version.

Algorithme 2 : méthode des queues minimales en O(N\log N)

Cette méthode est liée au patience sorting.

Idée

On maintient un tableau tails.

La case tails[k] contient la plus petite valeur finale connue pour une sous-suite croissante de longueur k+1.

Une petite valeur finale est avantageuse : elle laisse davantage de possibilités pour prolonger la sous-suite.

Pour chaque valeur x, on cherche par dichotomie la première position p telle que :

\text{tails}[p]\geq x.

On remplace alors tails[p] par x.

Si aucune position ne convient, on ajoute x à la fin.

Exemple sans reconstruction

Pour la suite

(4,2,7,3,8),

les états successifs sont :

4  -> [4]
2  -> [2]
7  -> [2, 7]
3  -> [2, 3]
8  -> [2, 3, 8]

La longueur finale de tails est 3.

Attention : tails ne contient pas nécessairement une sous-suite réelle de la suite d’origine. Il représente les meilleures valeurs terminales connues pour chaque longueur.

Pour reconstruire une véritable sous-suite, il faut mémoriser les indices et les prédécesseurs.

Reconstruction

On maintient :

tails_value[p] : meilleure valeur terminale pour une longueur p+1 ;
tails_index[p] : indice dans la suite d’origine de cette valeur ;
previous[i] : prédécesseur de l’élément d’indice i dans la sous-suite reconstruite.

Lorsqu’un élément a_i est placé à la position p :

son prédécesseur est tails_index[p - 1] si p>0 ;
il devient le nouvel indice terminal pour la longueur p+1.

Pseudo-code

fonction lis_n_log_n(a):
    N = longueur(a)

    tails_value = tableau dynamique vide
    tails_index = tableau dynamique vide
    previous = tableau de N cases initialisées à -1

    pour i de 0 à N - 1:
        x = a[i]

        p = première position telle que tails_value[p] >= x
            trouvée par recherche dichotomique

        si p == longueur(tails_value):
            ajouter x à tails_value
            ajouter i à tails_index
        sinon:
            tails_value[p] = x
            tails_index[p] = i

        si p > 0:
            previous[i] = tails_index[p - 1]

    fin = dernier élément de tails_index

    résultat = liste vide
    tant que fin != -1:
        ajouter a[fin] à résultat
        fin = previous[fin]

    renverser résultat
    retourner résultat

Complexité temporelle

Chaque élément est traité une fois.

Pour chaque élément, on effectue une recherche dichotomique dans un tableau dont la taille est au plus N.

Une recherche dichotomique coûte :

O(\log N).

Donc :

T(N)=N\cdot O(\log N)=O(N\log N).

La reconstruction coûte O(N) dans le pire cas, ce qui reste inférieur au coût principal.

Complexité mémoire

Les tableaux tails_value, tails_index et previous ont une taille au plus N.

Donc :

M(N)=O(N).

Comparaison des deux algorithmes

Méthode	Temps	Mémoire	Reconstruction	Difficulté
Programmation dynamique	O(N^2)	O(N)	Simple	Faible
Queues minimales avec dichotomie	O(N\log N)	O(N)	Plus délicate	Moyenne

La programmation dynamique est adaptée aux petites entrées et expose directement la structure mathématique du problème.

La méthode en O(N\log N) est préférable pour les grandes suites.

Sous-suite décroissante

Pour rechercher une plus longue sous-suite strictement décroissante, trois méthodes équivalentes sont possibles :

remplacer la condition a_j<a_i par a_j>a_i ;
appliquer l’algorithme croissant à la suite (-a_i) ;
adapter la recherche dichotomique pour maintenir des queues décroissantes.

Valeurs égales

L’énoncé initial suppose généralement les valeurs distinctes.

Pour des valeurs répétées, il faut distinguer :

sous-suite strictement croissante : a_{i_1}<a_{i_2}<\cdots ;
sous-suite croissante au sens large : a_{i_1}\leq a_{i_2}\leq\cdots.

Dans l’algorithme en O(N\log N) :

pour une sous-suite strictement croissante, on cherche la première position telle que tails[p] >= x ;
pour une sous-suite croissante au sens large, on cherche la première position telle que tails[p] > x.

Le choix entre lower_bound et upper_bound modifie donc le traitement des égalités.