Somme maximale de termes consécutifs

On considère un tableau non vide de nombre entiers, positifs ou négatifs, et on souhaite déterminer la plus grande somme possible de ses éléments consécutifs.

Par exemple, dans le tableau [1, -2, 3, 10, -4, 7, 2, -5], la plus grande somme est 18 obtenue en additionnant les éléments 3, 10, -4, 7, 2.

Pour cela, on va résoudre le problème par programmation dynamique. Si on note tab le tableau considéré et i un indice dans ce tableau, on se ramène à un problème plus simple : déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i.

Si on connait la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i - 1, on peut déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i :

  • soit on obtient une plus grande somme en ajoutant tab[i] Ă  cette somme prĂ©cĂ©dente ;
  • soit on commence une nouvelle somme Ă  partir de tab[i].

Remarque : les sommes considérées contiennent toujours au moins un terme.

Exemples

Python Console Session
>>> somme_max([1, 2, 3, 4, 5])
15
>> somme_max([1, 2, -3, 4, 5])
9
>>> somme_max([1, 2, -2, 4, 5])
10
>>> somme_max([1, -2, 3, 10, -4, 7, 2, -5])
18
Compléter le code ci-dessous

Compléter la fonction somme_max ci-dessous qui réalise cet algorithme.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013kg[: r);SĂ©/(lo4y,6b=ac1x5+ud3t28_Pw7evp-fh0*9mn]is050C0L0E0v0X0n0Y0f0w0n0v0Y0Y0u010E0X0N010406050Y0B0U0U0v0g0q040j0o0n0B0?0o0V050l0}0 11130{0N04051j1c1m0l1j0{0C0X0M0+0-0/0;0-0V0c0B0v0c0L0O0N0q0E0Q1a0f0Q0X0c0Q0n1O0Q0E0_050$0t0n0L1v0.0:011N1P1R1P0E1X1Z1V0E0g1k1J0+160Y0N0v0V0;0F011#1x010P0(0L0V0v0U0L1V1`1|211%241Z27290_0a0f0I0g0o0N0o0Y0X190V0f0!1^0g0g0L0w2u1c2c0V1k0l1J2H1;1?1=1W0C2e1y0X0V262r1V1s1u0,1$2R2T0V0o2X1V0N2A1k2F2H2.0|1{2v2Z222%0g100n1V0v1M2A0P0;030H0H0w2(0L1R2$0o0O0x3c0_0f0x1c0v2/2=0`2;2d2@1%2_2{2}2 0L3101333537392U3c0O1 040f0F3i3k1|3m2F2Q013r0v2|1k2~0Q303234360!3B2%3D0D3f0D3J2E3l0{3N3p0;3Q3S053U3W3x3Y3A2S3C3d0p3f0p3+1d3-3n2?1w3q0o2`3R3t3V3v3X3z3!3}3$3d0z3f0z432.3.2=3O3=4d3_3y3Z384j3b3d0s3f0s4p453/483;4a3s3T3u3w4x3|3a3D0K3f0K4G3L4r3o4J3P4L4c4N4e4P3{4i4S3d0G3f0G4X2G4Z472!4$4b3?3^4f3`4h4z4.0O0T3f0T4?3M4s3:4{4M3@4O4g4y3#4B3c0R0_0x0R584^4t4%4}5f505h4A3D0x0x5m3h0l3j3,4Y465r4|4v4 4Q4-3~3c3F0x3I5D3K4@5H5b4u4)4w4,525O0x3(045(5p5W4#5Y5e4*5g4R5%405*425T5F5V4I4`5/4~4+515i5y4m5*4o5{445G5~2^5s5K625w530x4D5*4F692:1p2,1c2X2K0C1?2P5b4y2W1t1k2+0L2-3l5|1k4y6E2d0X0C0;342F5y3t6L6N635x3d5A0f2i0L6T6h5%1V5{6c1%0b0_0!0P6G0f5-5 0P0_0Y0o0 0L0H100y6G6=220^040m706*3;0_1X765a4#730h0e6G0{6a2G5H6S016O2=3D3F5e7m5#643d1 6Y286!7n6U537r5T0f7G6;773P0_1b7j3G711%0o0_0u6:7P3;0t0_2h7b4!4`73757N7V7K047a7)7J7e7h7!2v7t0H6P3d5)7s6M7B6$4k0O3(7y296#5?807{7F7H7*0V6^6`290Y6}0v6 7N7I7c4`7R047T8k7*730d7=3O0U0X0_5o7.8m720_0W7U7J8o0S8G8C3q7L7;8B6K7}7o1|3D5^7|855N8040837A7u6V0O8V897G8b8d6{8g6~8v5b8t8=4#8x8z8^7$8E8K7#228o8q2.8l908M7,0v0t8|8D048u8P4_228`048A2:7/8~7N7i9l4s7@7_0O668W7~865j4m8#8X5$809v8+959g1%0w5A04030f1L0w3R0w0B1Z0f0-0f0N170*0c0g1|2x6_6{0f0Y1!0E0L2`2S1|0E0f260f0X8O9q8Q6T9t6k9w8%534D9B9x8Y5ja09G7*6,040P4a8 9I78049`8r8H0J0_2Sag4t7X049$1A0L9b1%7%ax0;9i5C9|ah01730raq5X8N9f3O7e7g9o8v9s7p3d4U4N7@7 5j4Ua5a25OaV3J7Ha*9H3Oac0X6/al8Lai9)8f8h8jaEaN0_9ea{aKajaJ4#8o0Ob24`aCaAaG9n947*8o0Ab62^7999b98@aMb0aka 7dbb3la,5b8o020c0E0ibg977-bp8}9db98cb1bmbq040WaP4qaR8R7^aT0O4:aWbQaY3D4:a#7C5ObUa)a+b)8-04a@0L8:8ibka}bGaob;bLbA0;92b`7+b-b/a`6F9mbFbJ5 b@a;96b{0_b5c8aFb8c59c8Fcd3Obeb}bHbCc2a=bac4bDbhbIctaybr5GaMaS8T3d55bV9C7v54206ZcG8(cEb(b*7Jac389,b^bN45cAbQ9t5n6RbW9y5y5lb!bX6W5l2H3jb)cPcqbHb a_b^a~cpc97+boc{aF73cibc8H7Scmbi9acgcxcsc 4tc7cw0;d19{dccB0V5y9La1b#805zcJ7zcL6idnaa7J9K0_9N1L9^0C0k0C0B2t9V2~9Y0B9!au9(8e1!2x0w381Z0Y0O0wc~cza{dk5y7r2~aXc%6W7xcKa69D5j5R6(c/8a7JbH6~0X0U0~b}b|cj5b9i9kcWd#cYbS5(c#du5%82d.a$dq88d@8,cQ0_ae0gd6cvbsbdanaj7Md3c=asau1Eb^7(df01cfeCaHeoeudc8?0_7fdi3L7le7cC3c8Vd)c$a75y8!eedpd;8*eia+abaoa:evc|c?dQc0c_b?epeOc3d2bsbtb30_bwbyeoc@8;d9dgb=f37+d{d}0Ub^bMeN7k3Nd$6W9veUebdq9AeZc+3c9Fe%c:e{c604f8d~e1e|8peodZ5VcX9~e8a0fjd/cH6jds84fJ8(fLc.3Gd^cqac2A0E0B0geI3Lftcuf1b:f6bleCd`8id|fxeFcyfD6o6I1n6q0l6s1c0E6uf}2N2I991Z2H6s7i0!0$0(0Y04.