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.
.128013l(9 _4:;=vm26-uS8ws*3/]+fr7gebh[pPicé05a,onkyd1x)t050U0D0Y0O0J0b0t0e0K0b0O0t0t0j010Y0J0H010406050t0p0l0l0O0A0T040q0Q0b0p0?0Q0R050w0}0 11130{0H04051j1c1m0w1j0{0U0J0k0+0-0/0;0-0R0C0p0O0C0D0o0H0T0Y0F1a0e0F0J0C0F0b1O0F0Y0_050$0E0b0D1v0.0:011N1P1R1P0Y1X1Z1V0Y0A1k1J0+160t0H0O0R0;0m011#1x010z0(0D0R0O0l0D1V1`1|211%241Z27290_0a0e0I0A0Q0H0Q0t0J190R0e0!1^0A0A0D0K2u1c2c0R1k0w1J2H1;1?1=1W0U2e1y0J0R262r1V1s1u0,1$2R2T0R0Q2X1V0H2A1k2F2H2.0|1{2v2Z222%0A100b1V0O1M2A0z0;030f0f0K2(0D1R2$0Q0o0V3c0_0e0V1c0O2/2=0`2;2d2@1%2_2{2}2 0D3101333537392U3c0o1 040e0m3i3k1|3m2F2Q013r0O2|1k2~0F303234360!3B2%3D0v3f0v3J2E3l0{3N3p0;3Q3S053U3W3x3Y3A2S3C3d0g3f0g3+1d3-3n2?1w3q0Q2`3R3t3V3v3X3z3!3}3$3d0N3f0N432.3.2=3O3=4d3_3y3Z384j3b3d0n3f0n4p453/483;4a3s3T3u3w4x3|3a3D0B3f0B4G3L4r3o4J3P4L4c4N4e4P3{4i4S3d0r3f0r4X2G4Z472!4$4b3?3^4f3`4h4z4.0o0d3f0d4?3M4s3:4{4M3@4O4g4y3#4B3c0M0_0V0M584^4t4%4}5f505h4A3D0V0V5m3h0w3j3,4Y465r4|4v4 4Q4-3~3c3F0V3I5D3K4@5H5b4u4)4w4,525O0V3(045(5p5W4#5Y5e4*5g4R5%405*425T5F5V4I4`5/4~4+515i5y4m5*4o5{445G5~2^5s5K625w530V4D5*4F692:1p2,1c2X2K0U1?2P5b4y2W1t1k2+0D2-3l5|1k4y6E2d0J0U0;342F5y3t6L6N635x3d5A0e2i0D6T6h5%1V5{6c1%0S0_0!0z6G5-4`0s3f6:6*3;0z0_0t0Q0 0D0f100W6^5a4#0^040c744!5 0_1X7a4_22770X0h6G0{6a2G5H6S016O2=3D3F5e7q5#643d1 6Y286!7r6U537v5T0e7K0e6;2^0_1b7n3G7N1%0Q0_0j6G7M6_3P0E0_2h7f3O77797R7T3;7d0O0E7)5b7i7l7)7x0f6P3d5)7w6M7F6$4k0o3(7C296#5?847 7J7L7.3P6|6~290t710O737R7Z754`7V047X8o8f770G7?4#0l0J0_5o7-7!770x7Y8f8s0u8J7!0R7P7_8F4s7{7}0o5^80895N8440877E7y6V8W6(3j7L8p7b7O046}6 8k728z4`8x8`228B8D8}1%8H8N8q228s8u2.8/7g3q7:7=8S8:920_8y9f9b0;8 048E2:8G0_8I7R7m9q8T817s1|3D668Y828a5j4m8%8Z5$849C8d7K8f0K5A04030e1L0K3R0K0p1Z0e0-0e0H170*0C0A1|2x8?290e0t1!0Y0D2`2S1|0Y0e260e0J8R9w6K9y7|7t4C6Ra4835j4D9I9E8!ab8,3G8e7!6,040z4a949g7/04a08v7!0Q6?as7Q998f0R7$049,1A0D910;7+aI019n5Ca29l01770PapaQ8P04az6F9r047ja1aZ9x6T8V4U4N7{aa4T206Z9J7z0oa,3J8.8.8fal0J6/au959c8=8i0D8^8maL8|9k4t0_ataAav0_0oaU3OaNb99sbj5b8s0ybo5.9dbm049jaPbcasbv9tbfb20;8s020C0Y0ibs7c047ebb7@9iaLaWbea(aqaR9s7k9u7`a48V4:a-a99F3D4:ad8)53b(a`a{b?aB8h8@8l8nbybQbwbSbdbBbL967Wc3b39/b6b{bvbxbVaVc1b1bW8sbicgaQblbP76bnck3Obqc6arbOb}cob cnbMbU3L8wcp4qb#a*a654a8a?8*55b.7G5O552H8-b?9a3Oal389=bvbZcFbb8UcI5ncKae9K5jc*cOa/6W5lcSaicUajbE8gb4b`8_cz7hbRd0b3cB7oa!bC3lcVbpc5cq5Xbud3aJd2cwcAc2b!c%b$c)9R9Db/5%6Xa=c,a@5zaha|7!9Q0_9T1L9~0U0L0U0p2t9#2~9(0p9*aF9.b52w1!0K381Z0t0o0Kd53mdncH9A6W7v2~a.b+d+a;7DcL6i7IcT9O8O0_720J0l0~ct0197e19n9p45d(7F8V5(c+ds84ebc:d/3c8cd_da4#alan0Ae1bTe1awbdaY3Lel5 aDaF1Ebv7,dj8~8C5*bvaTddbtaXbva$dmbyc(d*3c8Xd-b*af5y8$dvedc.8X9Na{a}bdb0bDbWaWc8b7b|cd7*die?debAdgbX04d8ewexc404bHbJeqb_8jcae|baeEb3d}d 0lbBc#e7eQdoeS0V9CeVd?5%9He!cPee9Mekc_b^04fee0eK8rdce-cee{c$fkd)0R5y6kdrfuc.acftc;3cfOe(e*aE0#0p0Aev2Gf1c7b5e;cbc0fA8md~fCfcdhe~a%cC0w6I1n6q0w6s1c0Y6ug12N2I7;1Z2H6s7m0!0$0(0t04.
# Tests
(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)