Exercice programmation dynamique : Longue Sous-séquence Croissante (LIS)

Énoncé

Étant donné un tableau d'entiers arr[] de taille N, l'objectif est de déterminer la longueur de la plus longue sous-séquence croissante (LIS) dans le tableau. Une sous-séquence croissante est définie comme une séquence dans laquelle chaque élément suivant est strictement supérieur à l'élément précédent. Le résultat attendu est la longueur de cette sous-séquence croissante.

Exemples de fonctionnement

1. Entrée : arr[] = {9, 1, 20, 18, 60}
Sortie attendue : 3
Explication : La plus longue sous-séquence croissante est {9, 20, 60}.
2. Entrée : arr[] = {30, 20, 10}
Sortie attendue : 1
Explication : Les sous-séquences croissantes sont {30}, {20}, et {10}.
3. Entrée : arr[] = {100, 100, 100}
Sortie attendue : 1
Explication : Il n'existe pas de sous-séquence strictement croissante.

Questions

  • Décrivez ce qu'est une sous-séquence croissante. Pourquoi n'incluons-nous pas les éléments identiques dans la sous-séquence ?
  • Proposez un algorithme  pour calculer la plus longue sous-séquence croissante dans un tableau de manière récursive et étudiez sa complexité ? Expliquez comment la mémorisation peut améliorer l’efficacité de la méthode récursive.
  • Pourquoi l’algorithme de recherche binaire améliore-t-il la complexité temporelle de la recherche de la plus longue sous-séquence croissante ?
  • Implémentez une fonction récursive pour calculer la longueur de la plus longue sous-séquence croissante se terminant à un indice donné. Adaptez cette fonction pour utiliser la mémorisation et Tabulation afin d’optimiser la solution.
  • Comparez les complexités temporelles des différentes méthodes (Récursion, Mémorisation, Programmation dynamique, et Recherche binaire). et Testez la fonction avec les tableaux suivants et notez les résultats : arr[] = {3, 10, 2, 1, 20}, arr[] = {30, 20, 10}, arr[] = {10, 20, 35, 80}.
Aucune note. Soyez le premier à attribuer une note !

Ajouter un commentaire

Anti-spam