Longest Increasing Subsequence
On te donne 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. Retourne 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
- 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-104 ≤ nums[i] ≤ 104
Exemples
- Entrée
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- Sortie
- 4
- Explication
- 1, 2, 5, 9 est une suite croissante, tout comme 1, 2, 5, 7 et 1, 2, 4, 7 : longueur 4. Aucun choix de cinq valeurs ne forme une suite croissante.
- Entrée
- nums = [7, 7, 7, 7]
- Sortie
- 1
- Explication
- Les valeurs doivent strictement augmenter, donc aucun des deux 7 ne peut se trouver dans la même sous-séquence. Un élément seul compte, ce qui donne une réponse de 1.
- Entrée
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- Sortie
- 4
- Explication
- -4, 0, 3, 16 a une longueur de 4. En partant du premier élément, 12, on n’obtient que deux valeurs, comme 12, 25 : la meilleure sous-séquence n’a pas besoin de commencer au début.
Pour aller plus loin
Peux-tu renvoyer une des plus longues sous-séquences croissantes elle-même, ainsi que sa longueur, tout en conservant une complexité de O(n log n) ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
La meilleure sous-séquence de toute la liste est difficile à décrire directement. Posons une question plus précise pour chaque indice
i: quelle est la plus longue sous-séquence croissante qui se termine exactement parnums[i]?Une sous-séquence se terminant à
nums[i]est soitnums[i]seul, soit prolonge la meilleure sous-séquence se terminant à un certainnums[j] < nums[i]antérieur. Choisis le meilleurjet ajoute un. La réponse est la plus grande de ces valeurs, quel que soit son point de terminaison.Pour passer sous
O(n²), ne gardez que, pour chaque longueur, la plus petite valeur avec laquelle peut se terminer une sous-séquence de cette longueur. Ces valeurs restent triées, donc une recherche binaire vous indique si un nouveau nombre prolonge la plus longue sous-séquence ou remplace une valeur de fin.
Solution
Une liste de n nombres possède 2^n sous-séquences, beaucoup trop pour toutes les vérifier. Demander, pour chaque indice, quelle est la longueur de la meilleure sous-séquence croissante qui se termine exactement à cet endroit donne un tableau en O(n²). La version la plus rapide conserve, pour chaque longueur, la plus petite valeur avec laquelle une sous-séquence de cette longueur peut se terminer, puis place chaque é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
Décidez pour chaque élément de le conserver ou non ; vous ne pouvez conserver nums[i] que s’il est supérieur à la dernière valeur conservée. longest(i, prev) est le nombre maximal d’éléments que vous pouvez encore ajouter à partir de l’indice i, lorsque le dernier élément conservé se trouve à prev (ou à -1). Passer donne longest(i+1, prev) ; conserver donne 1 + longest(i+1, i). Chaque sous-séquence croissante correspond à un chemin parmi ces choix.
Pour 1, 2, 3, ..., n, les deux branches restent ouvertes et le nombre d’appels double à chaque élément : 2^40 représente déjà environ 10^12. Pourtant, il existe au plus n² paires différentes (i, prev).
Algorithme
- Écris
longest(i, prev), oùprevest l’indice du dernier élément conservé, ou-1. - Si
idépasse la fin, retourne 0. - Ignore
nums[i]:best = longest(i+1, prev). - Si
prevvaut-1ou sinums[i] > nums[prev], conserve-le :best = max(best, 1 + longest(i+1, i)). - Retourne
best. La réponse estlongest(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)Plus longue sous-séquence se terminant à chaque indice
Intuition
Soit ending[i] la longueur de la plus longue sous-séquence croissante dont le dernier élément est nums[i]. L’élément qui précède nums[i], s’il y en a un, est un nums[j] tel que j < i et nums[j] < nums[i], et la partie jusqu’à cet élément doit être aussi longue que possible. Donc ending[i] = 1 + max(ending[j]) pour ces j, ou 1 s’il n’y en a aucun. Remplis le tableau de gauche à droite.
Pour [3, 1, 8, 2, 5, 9, 4, 7], le tableau est [1, 1, 2, 2, 3, 4, 3, 4] : 5 peut suivre 3, 1 ou 2, et la meilleure de ces possibilités a une longueur de 2, donc ending[4] = 3. La réponse est la plus grande valeur du tableau, puisque la meilleure sous-séquence peut se terminer n’importe où.
n(n-1)/2 comparaisons : environ 3.1 × 10^6 pour n = 2500.
Algorithme
- Créez
endingavec chaque entrée définie à 1. - Pour chaque
i, de gauche à droite, examinez tous lesj < i. - Si
nums[j] < nums[i], définissezending[i]surending[j] + 1si cette valeur est plus grande. - Retournez 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)Queues les plus petites avec la recherche binaire
Intuition
Pour chaque longueur, ne gardez que la plus petite valeur avec laquelle peut se terminer une sous-séquence croissante de cette longueur : tails[k] pour la longueur k+1. Une terminaison plus petite n'est jamais pire : tout ce qui peut suivre un 9 peut suivre un 5. tails reste strictement croissant : supprimez la dernière valeur d'une sous-séquence croissante de longueur k+2 et vous obtenez une sous-séquence de longueur k+1 qui se termine par une valeur plus petite.
Pour chaque x, effectuez une recherche binaire pour trouver la première queue ≥ x. S'il n'y en a pas, ajoutez x : il prolonge la plus longue sous-séquence. Sinon, remplacez cette queue par x : la sous-séquence de longueur inférieure d'une unité se termine par une valeur inférieure à x, donc x donne la même longueur avec une terminaison plus petite.
Par exemple, pour l'exemple 1, tails devient [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7] : longueur 4. Dans [1, 2, 4, 9], le 4 est arrivé après le 9, donc seule la longueur de tails a une signification.
Algorithme
- Commence avec une liste vide
tails. - Pour chaque
xdansnums, effectue une recherche binaire pour trouver le premier indicektel quetails[k] ≥ x. - Si aucune valeur de
tailsn'est≥ x, ajoutex. - Sinon, définis
tails[k] = x. - Renvoie 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
- Renvoyer
ending[n-1]au lieu de la plus grande entrée. Pour[1, 2, 3, 0], la dernière entrée 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 le premier tail
> xau lieu de≥ x. Le deuxième 7 est alors ajouté après le premier, ce qui compte les valeurs égales comme croissantes. - Résoudre par erreur la version contiguë. Dans l’exemple 1, la plus longue suite croissante de voisins est 2, 5, 9 (longueur 3), tandis que la réponse est 4.
- Conserver des index commençant à 0 en Lua ou en R, où les tableaux commencent à 1. Le marqueur
prev = -1devient 0, et la recherche binaire porte sur les index de 1 à la taille actuelle.
Questions fréquentes3
Quelle est la complexité temporelle de la plus longue sous-séquence croissante ?
La méthode des queues s’exécute en O(n log n) et utilise un espace O(n) : une recherche binaire par élément. Le tableau portant sur chaque paire d’index prend un temps O(n²), et essayer chaque sous-séquence prend O(2ⁿ).
Qu’est-ce que le tri par patience pour la plus longue sous-séquence croissante ?
C'est la méthode « tails », nommée d'après un jeu de cartes. Chaque queue est la carte du dessus d'une pile : une carte est placée sur la pile la plus à gauche dont la carte du dessus a une valeur au moins égale à la sienne, ou bien elle commence une nouvelle pile. Le nombre de piles est la réponse.
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, afin qu’une valeur égale prolonge la liste au lieu de remplacer une queue. [7, 7, 7, 7] renvoie alors 4.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def lengthOfLIS(nums):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
nums = [3, 1, 8, 2, 5, 9, 4, 7]
Résultat attendu
4