Longest Increasing Subsequence

Q: Quelle est la complexité temporelle de la plus longue sous-séquence croissante ?

La méthode des tails s’exécute en O(n log n) et utilise O(n) d’espace : une recherche binaire par élément. Le tableau de programmation dynamique sur chaque paire d’indices prend O(n²) en temps, et essayer chaque sous-séquence prend O(2ⁿ) . Pour n = 2500 , cela représente environ 30 000, 3 millions et un nombre astronomique d’étapes.

Q: Pourquoi la méthode du tri par patience donne-t-elle la bonne longueur ?

Après chaque élément, tails[k] contient la plus petite valeur avec laquelle peut se terminer toute sous-séquence croissante de longueur k+1 observée jusqu’ici. L’ajout ne se produit que lorsque x est supérieur à toutes les valeurs de fin, ce qui signifie qu’il existe désormais une sous-séquence plus longue d’un élément que toutes celles qui l’ont précédée. Le remplacement ne modifie jamais la longueur ; il ne fait que réduire une valeur de fin, de sorte que la longueur de la liste est toujours égale à celle de la plus longue sous-séquence croissante.

Q: Comment obtenir la véritable plus longue sous-séquence croissante, et pas seulement sa longueur ?

Enregistre un parent pour chaque élément. Dans le tableau O(n²) , le parent de i est le j qui a donné sa valeur à ending[i] . Dans la méthode des queues, stocke l’indice de l’élément situé derrière chaque queue et définis le parent d’un élément comme l’indice stocké une position à sa gauche lorsqu’il est placé. Remonte ensuite les parents à partir de la fin de la sous-séquence la plus longue et inverse le résultat.

Q: Comment trouver plutôt la plus longue sous-séquence non décroissante ?

Autorisez les voisins égaux. Dans le tableau, utilisez nums[j] ≤ nums[i] . Dans la méthode des queues, recherchez la première queue strictement supérieure à x au lieu d’une queue supérieure ou égale, afin qu’une valeur égale prolonge la liste au lieu de remplacer une queue. [7, 7, 7, 7] renvoie alors 4.

MoyenProgrammation dynamique Recherche binaire

+10

Vous obtenez une liste d’entiers nums. Une sous-séquence conserve certains éléments, dans leur ordre d’origine, et supprime les autres ; les éléments conservés n’ont pas besoin d’être côte à côte. Renvoyez la longueur de la plus longue sous-séquence dont les valeurs augmentent strictement de gauche à droite. Deux valeurs égales à la suite ne comptent pas comme une augmentation.

Fonction

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: la liste des entiers parmi lesquels choisir
Renvoieinteger: la longueur de la plus longue sous-séquence strictement croissante

Contraintes

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Exemples

Entrée: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Sortie: 4
Explication: Conserver 1, 2, 5, 9 donne une sous-séquence croissante de longueur 4, tout comme 1, 2, 5, 7 et 1, 2, 4, 7. Aucun choix de cinq valeurs ne reste croissant, donc la réponse est 4.

+20 tests cachés à la soumission

Pour aller plus loin

Pouvez-vous renvoyer une plus longue sous-séquence croissante elle-même, et pas seulement sa longueur, tout en conservant une complexité temporelle de O(n log n) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une sous-séquence peut ignorer n’importe quel élément ; une liste de n nombres en compte donc 2^n, ce qui est beaucoup trop pour toutes les vérifier. La solution par programmation dynamique consiste à poser une question plus précise pour chaque indice : quelle est la longueur de la meilleure sous-séquence croissante qui se termine exactement ici ? Cela donne un tableau en O(n²). La version la plus rapide conserve un nombre par longueur, soit la plus petite valeur à laquelle peut se terminer une sous-séquence de cette longueur, et place chaque nouvel élément à l’aide d’une recherche binaire.

Prendre ou ignorer chaque élément

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Parcours la liste et prends une décision pour chaque élément : le garder ou le laisser de côté. Tu ne peux garder nums[i] que s’il est supérieur à la dernière valeur que tu as gardée. Une fonction récursive longest(i, prev) répond à la question suivante : si le dernier élément gardé se trouve à l’indice prev (ou -1 si aucun élément n’a encore été gardé), combien d’autres éléments peux-tu ajouter à partir de l’indice i ?

En laissant l’élément de côté, on obtient longest(i+1, prev). En le gardant, lorsque c’est autorisé, on obtient 1 + longest(i+1, i). La réponse est la plus grande des deux, et une fois la fin de la liste atteinte, on ne peut plus rien ajouter : le résultat est donc 0. Chaque sous-séquence croissante correspond à un chemin de choix entre garder et laisser de côté ; la recherche ne peut donc pas passer à côté de la meilleure.

Cette méthode est lente, car les deux branches restent ouvertes chaque fois que les valeurs augmentent. Dans une liste comme 1, 2, 3, ..., n, le nombre d’appels double à chaque élément : 2 à la puissance 40 représente déjà environ 10^12 appels, et les grands tests comportent 2500 éléments. Pourtant, longest(i, prev) dépend uniquement de la paire (i, prev) : il n’y a donc au plus que n² questions différentes. La prochaine approche consiste à poser chacune d’elles une seule fois.

Algorithme

Écrivez longest(i, prev), où prev est l’indice du dernier élément conservé, ou -1.
Si i dépasse la fin, renvoyez 0.
Ignorez nums[i] : best = longest(i+1, prev).
Si prev vaut -1 ou si nums[i] > nums[prev], conservez-le : best = max(best, 1 + longest(i+1, i)).
Renvoyez best. La réponse est longest(0, -1).

def lengthOfLIS(nums):
    def longest(i, prev):
        # The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
        # prev is -1 while nothing has been taken.
        if i == len(nums):
            return 0
        best = longest(i + 1, prev)  # skip nums[i]
        if prev == -1 or nums[i] > nums[prev]:
            best = max(best, 1 + longest(i + 1, i))  # take nums[i]
        return best

    return longest(0, -1)

Sous-séquence la plus longue se terminant à chaque indice

Intuition

État. Soit ending[i] la longueur de la plus longue sous-séquence croissante dont le dernier élément est nums[i]. Fixer le dernier élément permet de décomposer le problème clairement : une fois que l’on sait où se termine une sous-séquence, on sait quelles valeurs ultérieures peuvent la suivre.

Récurrence. Si la sous-séquence se terminant par nums[i] comporte plus d’un élément, celui qui précède nums[i] est un nums[j] tel que j < i et nums[j] < nums[i], et la partie qui se termine par cet élément doit être aussi longue que possible. Ainsi, ending[i] = 1 + max(ending[j]) pour ces valeurs de j. Cas de base : chaque élément forme à lui seul une sous-séquence, donc ending[i] commence à 1. Ordre : ending[i] ne dépend que d’indices plus petits, il faut donc le calculer de gauche à droite.

Pour [3, 1, 8, 2, 5, 9, 4, 7], le tableau est [1, 1, 2, 2, 3, 4, 3, 4]. Par exemple, 5 peut suivre 3, 1 ou 2, et le meilleur de ces éléments est 2, avec ending = 2, donc ending[4] = 3. La réponse est la plus grande valeur du tableau, 4, et non la dernière : la meilleure sous-séquence peut se terminer n’importe où.

Chaque indice examine une fois tous les indices précédents, ce qui représente n(n-1)/2 comparaisons, soit environ 3.1 × 10^6 pour n = 2500.

Algorithme

Créez ending en définissant chaque élément à 1.
Pour chaque i, de gauche à droite, examinez chaque j < i.
Si nums[j] < nums[i], définissez ending[i] sur ending[j] + 1 si cette valeur est plus grande.
Renvoyez la plus grande valeur de ending.

def lengthOfLIS(nums):
    n = len(nums)
    # ending[i]: the longest increasing subsequence that ends with nums[i]
    ending = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
                ending[i] = ending[j] + 1
    return max(ending)

Les plus petites queues avec recherche binaire

Intuition

Le tableau ci-dessus mémorise une longueur par indice. Tu peux en mémoriser moins : pour chaque longueur, uniquement la plus petite valeur avec laquelle peut se terminer une sous-séquence croissante de cette longueur. Appelle-la tails[k] pour la longueur k+1. Une terminaison plus petite est toujours au moins aussi bonne, car toute valeur qui peut suivre une sous-séquence se terminant par 9 peut aussi suivre une sous-séquence se terminant par 5.

tails est toujours trié par ordre strictement croissant : une sous-séquence de longueur k+2 se terminant par t contient une sous-séquence de longueur k+1 qui se termine par une valeur inférieure à t. Ainsi, pour chaque nouvelle valeur x, effectue une recherche binaire pour trouver la première terminaison supérieure ou égale à x. S’il n’y en a pas, x est supérieur à toutes les terminaisons et prolonge la plus longue sous-séquence ; ajoute-le donc à la fin. Sinon, remplace cette terminaison par x : la sous-séquence d’une longueur inférieure se termine par une valeur inférieure à x, donc ajouter x donne la même longueur avec une terminaison plus petite.

Pour [3, 1, 8, 2, 5, 9, 4, 7], tails devient [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7], et sa longueur 4 est la réponse. À l’étape [1, 2, 4, 9], le 4 apparaît après le 9 dans l’entrée, donc tails n’est pas lui-même une sous-séquence ; seule sa longueur a un sens. Cette méthode est aussi appelée tri par patience, d’après le jeu de cartes où chaque terminaison est la carte du dessus d’une pile.

Chaque élément nécessite une recherche binaire parmi au plus n terminaisons : environ 2500 × 12 = 30,000 étapes pour l’entrée la plus grande.

Algorithme

Commencez avec une liste vide tails.
Pour chaque x dans nums, effectuez une recherche binaire pour trouver le premier indice k tel que tails[k] ≥ x.
Si aucune queue n’est ≥ x, ajoutez x.
Sinon, définissez tails[k] = x.
Renvoyez la longueur de tails.

from bisect import bisect_left


def lengthOfLIS(nums):
    # tails[k]: the smallest last value of any increasing subsequence of length k + 1
    tails = []
    for x in nums:
        k = bisect_left(tails, x)  # the first tail that is >= x
        if k == len(tails):
            tails.append(x)  # x extends the longest subsequence so far
        else:
            tails[k] = x  # x is a smaller ending for length k + 1
    return len(tails)

Pièges et cas limites

La plupart des mauvaises réponses viennent d’une confusion sur ce que contient le tableau ou du fait de considérer que des valeurs égales sont croissantes.

Retourner ending[n-1] au lieu de la plus grande valeur. Pour [1, 2, 3, 0], la dernière valeur est 1, mais la réponse est 3.
Comparer avec ≤ au lieu de <. [7, 7, 7, 7] doit renvoyer 1, et non 4.
Dans la version avec tails, rechercher la première queue > x au lieu de ≥ x. En présence de doublons, cela ajoute le deuxième 7 après le premier et compte les valeurs égales comme une sous-séquence plus longue.
Considérer tails comme étant la sous-séquence elle-même. Ses valeurs peuvent provenir de différentes sous-séquences ; ne l’affiche donc que si tu suis les parents séparément.
Résoudre par erreur la version contiguë. Dans [3, 1, 8, 2, 5, 9, 4, 7], la plus longue suite croissante de valeurs voisines est 2, 5, 9 (de longueur 3), alors que la réponse est 4.
En Lua et en R, les tableaux commencent à 1 ; un marqueur prev = -1 basé sur un index commençant à 0 devient donc 0, et la recherche binaire s’effectue sur les index de 1 à la taille actuelle.

Questions fréquentes4

Quelle est la complexité temporelle de la plus longue sous-séquence croissante ?

La méthode des tails s’exécute en O(n log n) et utilise O(n) d’espace : une recherche binaire par élément. Le tableau de programmation dynamique sur chaque paire d’indices prend O(n²) en temps, et essayer chaque sous-séquence prend O(2ⁿ). Pour n = 2500, cela représente environ 30 000, 3 millions et un nombre astronomique d’étapes.

Pourquoi la méthode du tri par patience donne-t-elle la bonne longueur ?

Après chaque élément, tails[k] contient la plus petite valeur avec laquelle peut se terminer toute sous-séquence croissante de longueur k+1 observée jusqu’ici. L’ajout ne se produit que lorsque x est supérieur à toutes les valeurs de fin, ce qui signifie qu’il existe désormais une sous-séquence plus longue d’un élément que toutes celles qui l’ont précédée. Le remplacement ne modifie jamais la longueur ; il ne fait que réduire une valeur de fin, de sorte que la longueur de la liste est toujours égale à celle de la plus longue sous-séquence croissante.

Comment obtenir la véritable plus longue sous-séquence croissante, et pas seulement sa longueur ?

Enregistre un parent pour chaque élément. Dans le tableau O(n²), le parent de i est le j qui a donné sa valeur à ending[i]. Dans la méthode des queues, stocke l’indice de l’élément situé derrière chaque queue et définis le parent d’un élément comme l’indice stocké une position à sa gauche lorsqu’il est placé. Remonte ensuite les parents à partir de la fin de la sous-séquence la plus longue et inverse le résultat.

Comment trouver plutôt la plus longue sous-séquence non décroissante ?

Autorisez les voisins égaux. Dans le tableau, utilisez nums[j] ≤ nums[i]. Dans la méthode des queues, recherchez la première queue strictement supérieure à x au lieu d’une queue supérieure ou égale, afin qu’une valeur égale prolonge la liste au lieu de remplacer une queue. [7, 7, 7, 7] renvoie alors 4.

Python

def lengthOfLIS(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Attendu

Longest Increasing Subsequence

Fonction

Contraintes

Exemples

Indices

Solution

Prendre ou ignorer chaque élément

Sous-séquence la plus longue se terminant à chaque indice

Les plus petites queues avec recherche binaire

Pièges et cas limites

Questions fréquentes4

Problèmes similaires