Plus longue sous-séquence croissante
DP en O(n^2), puis l’astuce en O(n log n)
Plus longue sous-séquence croissante est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Ce qu'est une LIS
Une sous-séquence conserve l'ordre, mais ignore certains éléments. La plus longue sous-séquence croissante est la plus longue de ces suites qui augmente strictement.
a = [3, 1, 4, 1, 5, 9, 2]Sous-séquence, pas sous-tableau
Contrairement à un sous-tableau, une LIS n'a pas besoin d'être contiguë. Vous pouvez sauter des nombres plus petits pour continuer à faire croître la chaîne.
L'état de DP en O(n²)
Soit dp[i] la longueur de la LIS qui se termine à l'indice i. Chaque élément constitue à lui seul une sous-séquence d'au moins une longueur.
dp = [1] * nLa transition en O(n²)
Pour chaque i, examinez chaque j antérieur. Si a[j] est plus petit, prolongez la sous-séquence : dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Lisez directement la réponse
Le résultat est la plus grande valeur de la table, puisque la LIS peut se terminer n'importe où, et pas seulement au dernier indice.
answer = max(dp)Pourquoi O(n²) peut dépasser la limite de temps
La double boucle coûte O(n au carré). Pour un n proche de 100000, c'est beaucoup trop lent et vous obtenez un verdict de limite de temps.
L'idée du tri par patience
La méthode plus rapide conserve, pour chaque longueur de sous-séquence, une liste du plus petit dernier élément possible, comme dans le tri par patience.
tails = []Utilisez bisect pour placer les éléments
Pour chaque nombre, effectuez une recherche binaire afin de trouver sa place parmi les derniers éléments avec bisect_left, pour un coût total en O(n log n).
from bisect import bisect_leftProlongez ou remplacez
Si la position se trouve après la fin, utilisez append pour agrandir la LIS. Sinon, remplacez ce dernier élément par la valeur plus petite.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLa longueur se trouve dans les derniers éléments
À la fin du parcours, len(tails) est la longueur de la LIS. La liste elle-même ne constitue pas toujours la sous-séquence ; seule sa longueur est exacte.
answer = len(tails)Strictement croissante ou non décroissante
Pour la variante non décroissante, remplacez-la par bisect_right afin que les valeurs égales puissent prolonger la chaîne.
from bisect import bisect_rightVérification rapide
Quelle méthode trouve la longueur de la LIS en O(n log n) ?
Récapitulatif : de n² à n log n
Vous pouvez maintenant résoudre la LIS de deux façons. Le DP en O(n²) est simple ; la méthode fondée sur les derniers éléments et bisect s'adapte aux grandes entrées et respecte la limite de temps.
Questions Fréquemment Posées
La leçon « Plus longue sous-séquence croissante » est-elle gratuite ?
Oui — le texte complet de « Plus longue sous-séquence croissante » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Plus longue sous-séquence croissante » ?
DP en O(n^2), puis l’astuce en O(n log n) Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Plus longue sous-séquence croissante » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Mémoïsation contre tabulation
- Définir l’état et la transition
- Escaliers et combinaisons de pièces
- Plus longue sous-séquence croissante