Exercice 3 - Partie B (Programmation dynamique) · Bac Numérique et Sciences Informatiques Amérique du Nord 2026 (jour 1)

Partie B

On considère une route perpendiculaire à la mer et des immeubles construits le long de cette route. On dit qu'un immeuble, d'un certain nombre d'étages, bénéficie d'une vue sur la mer lorsque les immeubles situés entre lui et la mer ont moins d'étages que lui. On souhaite que les immeubles de la rue aient tous au moins un appartement avec vue sur mer en détruisant le moins d'immeubles possible.

Pour résoudre ce problème, on considère la liste des nombres d'étages de chaque immeuble de cette rue, en partant de la mer: il s'agit de trouver ce qu'on appelle une sous-séquence strictement croissante de longueur maximale de cette liste.

Une sous-séquence d'une liste est une suite d'éléments obtenue en supprimant certains éléments, éventuellement aucun, de la liste d'origine sans changer l'ordre des éléments restants.

Exemples: pour la liste L1 = [10, 22, 9, 33, 21, 50, 41, 60], les listes [22, 9, 50], [10, 22] ou [33] sont des sous-séquences.

La longueur d'une sous-séquence est son nombre d'éléments.

On appelle sous-séquence strictement croissante d'une liste une sous-séquence telle que chaque élément est strictement supérieur au précédent.

Exemples: pour la liste L1 précédente,

[10] est une sous-séquence strictement croissante de longueur 1;

[9, 33] est une sous-séquence strictement croissante de longueur 2;

[10, 22, 33, 50, 60] est une sous-séquence strictement croissante de longueur maximale de L1; elle est de longueur 5.

Pour les questions suivantes, on définit la liste L2 = [3, 1, 8, 2, 5].

Programmation dynamique

Afin de résoudre le même problème, cette fois-ci on utilise la programmation dynamique. On cherche à écrire la fonction llsc_dyn.

Principe:

on crée une liste dyn telle que dyn[i] contient la longueur d'une plus longue sous-séquence strictement croissante se terminant à l'indice i;

pour chaque i, on parcourt les indices j < i et si tab[j] < tab[i], on met à jour dyn[i].

12.

Recopier et compléter les lignes 7 et 8 de la fonction llsc_dyn. On pourra utiliser la fonction native de Python max qui renvoie le maximum des valeurs données en paramètres.

1 def llsc_dyn(tab):

2 n = len(tab)

3 dyn = [1] * n

4 for i in range(1, n):

5 for j in range(i):

6 if tab[j] < tab[i]:

7 dyn[i] = max(...,...)

8 return...

13.

Citer un avantage de cette implémentation par rapport à l'implémentation récursive.