trouver la plus longue sous-séquence croissante (LIS)

Question

Étant donné A = {1,4,2,9,7,5,8,2}, trouver le LIS. Montrez la table de programmation dynamique remplie et comment la solution est trouvée.

Mon livre ne couvre pas LIS donc je suis un peu perdu sur la façon de commencer. Pour la table DP, ive a fait quelque chose de similaire avec les plus longues sous-séquences communes. Toute aide sur la façon de commencer cela serait très appréciée.

Answer 1

Déjà beaucoup de réponses sur ce sujet mais voici ma procédure pas à pas, je vois ce site comme un référentiel de réponses pour la postérité future et c'est juste pour fournir des informations supplémentaires lorsque j'ai travaillé à travers moi. Le plus long problème de sous-séquence croissante (LIS) consiste à trouver la longueur de la sous-séquence la plus longue d'une séquence donnée de sorte que tous les éléments de la sous-séquence soient triés dans l'ordre croissant. Par exemple, la longueur de LIS pour

{ 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}. 

Soit S[pos] être définie comme le plus petit entier qui se termine une suite croissante de longueur pos.

maintenant itérer tout entier X de l'ensemble d'entrée et procédez comme suit:

Si X> dernier élément de S, puis append X à la fin de S. Cela signifie que nous avons essentialy trouvé un nouveau plus LIS .

Sinon, trouvez le plus petit élément dans S, qui est> = que X, et changez-le en X. Comme S est trié à tout moment, l'élément peut être trouvé en utilisant la recherche binaire dans log (N).

exécution totale - entiers N et une recherche binaire pour chacun d'eux - N * log (N) = O (N log N)

Maintenant, nous allons faire un exemple réel:

des entiers: 2 6 3 4 1 2 9 5 8

étapes:

0. S = {} - Initialize S to the empty set 
1. S = {2} - New largest LIS 
2. S = {2, 6} - 6 > 2 so append that to S 
3. S = {2, 3} - 6 is the smallest element > 3 so replace 6 with 3 
4. S = {2, 3, 4} - 4 > 3 so append that to s 
5. S = {1, 3, 4} - 2 is the smallest element > 1 so replace 2 with 1 
6. S = {1, 2, 4} - 3 is the smallest element > 2 so replace 3 with 2 
7. S = {1, 2, 4, 9} - 9 > 4 so append that to S 
8. S = {1, 2, 4, 5} - 9 is the smallest element > 5 replace 9 with 5 
9. S = {1, 2, 4, 5, 8} - 8 > 5 so append that to S 
So the length of the LIS is 5 (the size of S). 

Prenons quelques autres séquences pour voir que cela couvrira toutes les mises en garde possibles, chacun présente sa propre question

dire que nous avons 1,2,3,4,9,2,3,4,5,6,7,8,10

fondamentalement, il construit sur 12349 d'abord, puis 2 remplacera 3, 3 remplacera 4, 4 remplacera 9, puis append 5,6,7,8,10 donc ressemblera 1,2,2,3,4,6,7,8,10

prendre la l'autre cas nous avons 1,2,3,4,5,9,2,10 cela nous donnera 1,2,2,4,5,9,10

ou prendre le cas, nous avons 1,2,3,4,5,9,6,7,8,10 cela nous donnera 1,2,3,4,5,7,8,10

afin que illumine genre de ce qui se passe, dans le premier cas, le moment critique étant ce qui se passe quand vous frappez la 2 après la 9, comment faire vous faites face à ceux-ci. bien le bloc de 2,3,4 ne fera rien vraiment, quand vous frappez 5 vous remplacez la 9 parce que le 5 et 9 sont pratiquement indifferentiable 9 se termine le bloc des premiers éléments 5 de plus en plus, vous remplacez 9 avec 5 parce 5 est plus petit donc il est plus grand potentiel de frapper quelque chose>5 plus tard. mais vous ne remplacez que le plus petit élément> lui-même. par ex. dans le dernier cas, si votre 6 ne remplace pas 9 mais remplace la place 1 et 7 remplace 2 et 8 remplace 3, nous obtenons un tableau final de 7 éléments au lieu de 9. Bougez donc deux de ces derniers et figure Sur le modèle, cette logique n'est pas la plus facile à traduire en papier.

Answer 2

Il existe une très forte relation entre LIS et LCS.

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Cet article explique assez bien je pense. Fondamentalement, l'idée est, vous pouvez réduire un problème à l'autre (c'est le cas dans de nombreuses situations impliquant la programmation dynamique).