Somme maximale de la racine à une feuille

🏷️ On considère ici des arbres étiquetés.

Les sommes, même pour un terme

Dans cet exercice (et les suivants), on considère qu'une somme peut avoir un ou plusieurs termes, mais pas zéro terme.

Dans le cas d'un arbre réduit à un seul nœud, la racine est également une feuille et on considèrera donc que cette valeur est une somme d'une seule valeur : de la racine à une feuille.

Pour un arbre en général, on s'intéresse aux sommes des valeurs de la racine jusqu'à une feuille quelconque. On en cherche la somme maximale.

Exemple

graph TB
    N0("4")
    N10("-5")
    N11("-3")
    N12("-2")
    N20("7")
    N21("-3")
    N22("-4")
    N23("0")
    N30("-1")
    N0 --- N10
    N0 --- N11
    N0 --- N12
    N10 --- N20
    N10 --- N21
    N11 --- N22
    N11 --- N23
    N20 --- N30

Les différentes somme de la racine à une feuille sont :

$4 + (-5) + 7 + (-1) = 5$
$4 + (-5) + (-3) = -4$
$4 + (-3) + (-4) = -3$
$4 + (-3) + 0 = 1$
$4 + (-2) = 2$

La somme maximale parmi ces sommes est $5$

Exercice

Coder une fonction somme_max_1 qui prend un arbre étiqueté (avec des entiers relatifs) en paramètre et qui renvoie la somme maximale des valeurs de la racine à une feuille de l'arbre.

Indice

C'est facile à coder !

Il faut juste renvoyer un entier :

Si la racine est une feuille, cette valeur commune. (1 terme dans la somme)
Sinon, de manière récursive, la racine augmentée du maximum des sommes maximales associées aux sous-arbres.

Évaluations restantes : ∞/∞

.9888.128013x/.r;nbylaeêu)dV63m(Pô+02-@,59fq78 _o=pcwgv41kRIéhtsSàji:050q0m0!0l0)0k0#0K0P0k0l0#0#0N010!0)0O010406050#0o0u0u0l0f0j040$0M0k0o0~0M0h0K020l0u0O0g0K0W0m180f0H0o0m0#050d1517191b130O04051G1z1J0d1G130q0)0S0?0^0`0|0Z0)0R0Z0k1X0Z0!11050.0i0k0m1S0_0{011W1Y1!1Y0!1*1,1(0!0f1H0!0Z1.1U010G0:0m0h1m0m010?1e0#0O0l0h0|0A1(2e2g221:251,280u2a040b0K0w0f0M0O0M0#0)1h1j0,2c0f0f0m0P2E1z2l0h1H0d202Q1}1 1~1)0q2n0|1!0h272B1(1P1R0@1/2!0)2$0h0M2*1(0O2J1H2O2Q2{142f1j2,232;0f180k110U2N2 122~2m311:3335110A392g3b2O2Z013g0l36040t3k2P133n3e0|3q3s0T3v3m2 3o3B110E3E3x3G3z3p0M343r110s3L3c301T3f3Q3h040I3V3y3Y3A3!3S040J3(3N3*3P3R3s0F3E1K2_1z2*2T0q1 2Y3O0P2=2t0+1Q1H2^0m2`3a3`440,4c3d3=0V110,0G3`3)2-010Q110K4o3;4q0h0G110#0M170m0L180c0L381A4d4p2310040v4v4i4x11190i2J4R3X4q4O0p0*3L0K4)4u4M1:0#2j04010w0M0o0f0K0o1j4V2J0K0q1i0h0Y0D0K2J0h0S0M0)1-0^0K4B4D0K4G0)351-2G5b0f0l0P2/1-0%4_2$0K0G0m0o0:1{4(4*3W3H115m5o2$4Y3o4O0D3E4+4w3211270G2g0!1y4K3l5N4S230M110N5M5C3O0h4U0f4W0m5A4)5)4j110)4n5W2P5Y4Z320i112q5I3O4O4Q5`4h5}3f5Q4y5T5V2}4,0|4#5(6f015#040N5%665|3o0u0)110z623=4O4%66064*6C6q3O4k042J0!4@0h6i5O696H5n5p5:6E5?040m0;5/665=4!116z2{6B6D5;6j6G6I6K6M5Z6O5F6R6p6!5!110y6:683A5 044G6w6#4P6S6*6+6N3A4A4C2s4F0l4H4J6e790164735P044B0o0#0L4|6Y7i6;6g110p6}3o6G0G3Q7A5*7b7q7s5-4X6^6j0M4s042/7F3=5+6V6b0h5U765B6j6h6A1z4f4b3{7*0d3~1z0!407/2W2R0l1+7,3~1F673o2J0u0L5S0V4E0Z0t111r1t1v1x0K6%4d1M3b0,0.0:0=3O0q2g0R0m0f113x161t1b0r190)5T1-0l0S2K5c0!0j1,5u1i2L0)506W4u1s040Z5n0V0j1z8P2N8t1D8g1Q3o1=1Z1#1%7}3O2p2729112v0$0P0f0 0!2w0j201i3`4a672|4d7)8+6U4m7m1:7P4u6Z6j4y7b4D7e7g977x759b7j7U7t9i7k7y8d3l6)787w014.114;4?4^4`0K7t4~5052542757590K5b5d2s5f7f5h3r5j5a0l546Q5t5r4`1-5v5x0k5z6A6C6_6=9Z7u4L7j5K7S4T7V5S7X6d3a6T4q6l6o2{9 7n9o9,7!7j6-0-6/7M9m5E9:9^6`046|ad9w0h70729l9w7la76*9.9j657v6~3p9e7d4G4I9pasay5D7o4?7ra6aH637yah1:7C7Ealaz7U7paL7K9;5Xav6k7P7RaUaI5R6caF7y5Lat6Da$7U4m0l0o0k0!9pa19p6s6u6Sa$7$6(7(452Q8 3}487|055h0R9Ea{0|0a2b3O0!0Q1s0M0(6t5c0f0P1V1_0O0#0*0d0d0P0q0h0e0(0#0,1!0S0f0e2$0!0d1Y0d0(0,0P830q2Rbn0ubp0)0C0U0E0e0U0e0z0d1/0-0#1A0S0R0d0A0s0l0z0e0#b=2b0~0!1,0|0*0Q190h2/0R0*010d040K0X0k0K5t5S1g5c4@0!4?8_2f0=274~0Y0q5x4}8a9N1-5g0u164~009$9N0)0#0!1-0S0)2G0,bK0/8_0n1}1-0z0K2f4^0q0Ycj8_cs0R0Y515m0k530P1-0#8pcRcX1f0!0x8_a$8x2018cK0c11090v0B092/0G8F097z6653cy0k001icX5w8_0Y8?0)4}cs0w8{0Zdh057)8$1#1@1$2k9m700G0k0M0la|aqazaG9=9w9y4:0Bd701a.04db2}bBb70e1K3b1G0X5o530:5ua_8_1g0:cI8p5s4u93a^a`0!0N6vdW4g532G4B0fcK0Kcy2C9N002D0Y5m7_0K1x8_cM0,538H0f0Y15a{dG0K0v0z0p5c000l0(co5q9N9X6?2$dY8f137-0-0/0;3beF8ieI.