Longueur maximale d'intervalle équilibré⚓︎
On considère une liste bits constituée uniquement de 0 et 1. Écrire une fonction telle que l_max_equilibree(bits) renvoie la longueur maximale d'une tranche qui contient autant de 0 que de 1.
Exemples
>>> bits = [0, 0, 1, 0, 0, 0, 1, 1, 0, 0]
>>> l_max_equilibree(bits)
6
[1, 0, 0, 0, 1, 1] est équilibrée et de longueur maximale.
>>> bits = [1, 1, 1, 1]
>>> l_max_equilibree(bits)
0
[] est équilibrée et de longueur maximale.
>>> bits = [1, 0, 1, 0, 1]
>>> l_max_equilibree(bits)
4
[1, 0, 1, 0] est équilibrée et de longueur maximale. Il y a également [0, 1, 0, 1] équilibrée et aussi de longueur maximale.
On écrira ici un algorithme qui fait une double boucle. Vous retrouverez ensuite cet exercice à faire avec une simple boucle.
Indice 1
On pourra construire une liste des cumuls du nombre de 1 de l'indice 0 jusqu'à l'indice i exclu.
Par exemple, avec bits = [1, 1, 0, 0, 1],
on aurait cumul = [0, 1, 2, 2, 2, 3] qui possède un élément de plus que bits.
Indice 2
On pourra faire une boucle pour tous les indices de fin d'une tranche et pour chaque indice de fin, une boucle pour chaque indice de début possible.
Indice 3
Pour un indice de début et de fin, on a une largeur de tranche et on peut avec une soustraction de deux valeurs de cumul connaitre le nombre de 1. On peut donc facilement savoir si la tranche est équilibrée.
Indice 4
On pourra compléter le code
def l_max_equilibree(bits):
cumul = [0]
for x in bits:
cumul.append(...)
l_max = ...
for i_fin in range(...):
for i_debut in range(...):
if ...:
if ... > l_max:
l_max = ...
return ...
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)