1-      Nous avons discuté des sous-problèmes de chevauchement et des propriétés optimales de la sous-structure. Discutons le problème de la plus longue augmentation de sous-séquence (LIS) en tant qu’exemple de problème pouvant être résolu à l’aide de la programmation dynamique.

Le problème de la plus longue 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 par ordre croissant. Par exemple, la longueur de LIS pour {10, 22, 9, 33, 21, 50, 41, 60, 80} est de 6 et LIS est de {10, 22, 33, 50, 60, 80}. 

Exemples :

entrée  : arr[] = {3, 10, 2, 1, 20}

sortie : longueur = 3

la plus longue sous sequence est 3, 10, 20

entrée  : arr[] = {3, 2}

sortie : Length of LIS = 1

la plus longue sous sequence est de {3} and {2}

entrée : arr[] = {50, 3, 10, 7, 40, 80}

sortie : la longueur = 4

la plus longue sous sequence croissante est  {3, 7, 40, 80}

fonction LIS(arr[1..n] tableau d’entier, n, max :entier) : entier

var i, res, max_endß1 ;

debut

// cas de base

si (n=1)  alors retourner 1 ;

pour iß1 à n faire debut

                        resßlis(arr, i, max) ;

                                     si (arr[i-1] < arr[n-1] && res+1> max_end) alors max_end=res+1 ;

fin pour

si(max<max_end) alors maxß max_end ;

retourner max_end ;

fin fonction LIS

fonction LIS1(arr[1..n] tableau d’entier, n : entier) : entier

var max=1 : entier ;

debut

lis(arr, n, max) ;

retourner max ;

}