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

🐍 Console Python

>>> bits = [0, 0, 1, 0, 0, 0, 1, 1, 0, 0]
>>> l_max_equilibree(bits)
6

En effet, la tranche [1, 0, 0, 0, 1, 1] est équilibrée et de longueur maximale.

🐍 Console Python

>>> bits = [1, 1, 1, 1]
>>> l_max_equilibree(bits)
0

En effet, la tranche [] est équilibrée et de longueur maximale.

🐍 Console Python

>>> bits = [1, 0, 1, 0, 1]
>>> l_max_equilibree(bits)
4

En effet, la tranche [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.

Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0lyq n7apS.r1-me,(P2=4:+twki9][5h*x)6050j0E0N0w0Q0q0b0t0i0q0w0b0b0J010N0Q0x010406050b0k0D0D0w0A0r040y0d0q0k0@0d0u050o0~1012140|0x041d1k051n0o1n1p1k0|0j0Q0m0,0.0:0=0V0Q0n0V0q1D0V0N0`050%0h0q0E1y0/0;011C1E1G1E0N1M1O1K0N0h0d0j141L0A1l0N0V0,170b0x0w0u0=0I011Q1A010l0)0E0u0w0D0E1K1=1@1|1S1 1O22240`0a0t0H0A0d0x0d0b0Q1a0u0t0#1:0A0A0E0i2p1d270u1l0o1.2C0N1,1+1-0j290=1G0u212m1K1v1x0-1R2M0Q2O0u1(1w1K0x2v1l2A2C2*0}1?2q2U1}2Z0A110q0`0t0B2z2.0{2-282:1S2=2@2_0I2|1@2~2A2L01330w2^040t0c372B0|3a310=3d3f0t0K3j392.3b3p2_0U3t3l3v3n3c0d2?3e2_0Z3A2 2/1z323F343g0v3K3m3N3o3P3H3g0f3T3C3V3E3G3q0R3#303%3x040B0p3,3M2V3(3Q0B2{1e2}3B3-3^3/0B363}383 3@2;3X3f0B3i453k3L3w4a0`0B3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0B3+4K4o3O4w0I3=4Q484S3Q0I3|2,1q2(1d2S2F0j2J3b0i1(251l4*1o4(4$2,4/0#2)4L1}0P0`0#0l3t4A3%0O2_544F2;0l0`0q0e110X0e0E0s0k0)0Q0h2v0E594~1S0_040G5r4R3o0`0h2o0b5x4X0=5u0Y0L3A0t5L0t55410`0i0 0k0q3t5N5a1S0d0`0J5V5O1}5u0T5E3b0D0Q0`4V2,5X5G0`0S5K5M5%1S50040l3F5$5=3c0`0X615s0=0d57042X665y63045B0N5D4m5{5?045J4t5M6q5W676f5R0D5T5+3D5Z040z6y3.0`0w0x0x210j6D3^5u5w6k620u5Q5S5U6P6t5)6L1}6A0C6Y1S5-4j6$6m5^4m6s6e6A0M6d5F6f656V6e5H5_5L6l6f5e5g6=3b6A5#6-6~6(045:3~6q6~5}5 0A724B0`0Q0e1 1c7662697j7n2*6.6?0u0h0`0A1@0n5q6_6?6N6*01784#2}6~5u0F7h3%7I7G6:7G7w5d217G7F7D3w5A5C7X0`0Y5I6|6r7d0`7f7O5P6b0e0#0h197:6Z6a6c7o6t7U047z0u7B7%5v7T7j7l7}5;6W7(6o2*066r8h7u3b5}0Q537~6e78448b6/0`0W856O8s7v6S6w6U8y3b6X7Z7i7=7m856,7t6~6!7`328A6x8G3%8F8D8H7k7@7_8T6M5@0Y8P685!758M6Q888J8o6?8O8;7!7=8Z0N858e7b8i8 7-6b8n8-7 8/8a2}8j6z0`6#8@8X7?0E7^8{9d3%6A020n0N0g8)6 5f0w6^8W8U0`8}468 9A5`8.04709t9q749q6R8I9738999k9b9J888`7+912v0N0k0A7s986~9K9F9u3~069+4u3D0i0B0`030t0N0E0b6i3?8k6F0:0E0A9i946e9%9s5h5j5l1G5o0E7C9v8$5v5*8#1}787a387L0`7N9j3^aj85aoa26?7Qah5tan9qarax6mat9#62aBad5(azapai5.79asaAaN7Jal627MaQ6)aC01aVaL6%aNak2Bam04aE9N77a%8K8(a#8*040J8,aF6t784y8f9-3%5}1R9 a1a`a35da55i5k5maaac7KaU0`0GagaIa$aXbjaDaW3:aPa=7HaRbqau5,btaY5u0Sa;bv9aa@a_a-aGa/4ta 3^b19~a09R9Eb8a7bb5p8wbibea{bxbmaZaKbC7PbIb!a!b%aqbZbX6`b$b5avb)b/7Eb;bGbYblb^8E8%9H8+bo4l8f1d4{0E2C2%c84)1w4+2F2H2D1%1)2F0w1Ncb0o4*0|co0$0(0*04.

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

🐍 Script Python

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 ...