/** Ċ Ġ* ĠP 1 8 - Maximum ĠPath ĠSum Ċ Ġ* ĠBy Ġstarting Ġat Ġthe Ġtop Ġof Ġthe Ġtriangle Ġbelow Ġand Ġmoving Ġto Ġadjacent Ġnumbers Ġon Ġthe Ġrow Ġbelow , Ġthe Ġmaximum Ġtotal Ġfrom Ġtop Ġto Ġbottom Ġis Ġ 2 3 . Ċ Ġ* ĠĠĠĠĠĠ 3 Ċ Ġ* ĠĠĠĠĠĠ 7 Ġ 4 Ċ Ġ* ĠĠĠĠĠĠ 2 Ġ 4 Ġ 6 Ċ Ġ* ĠĠĠĠĠĠ 8 Ġ 5 Ġ 9 Ġ 3 Ċ Ġ* ĠThat Ġis , Ġ 3 Ġ+ Ġ 7 Ġ+ Ġ 4 Ġ+ Ġ 9 Ġ= Ġ 2 3 . Ċ Ġ* ĠFind Ġthe Ġmaximum Ġtotal Ġfrom Ġtop Ġto Ġbottom Ġof Ġthe Ġtriangle Ġbelow : Ċ Ġ* ĠĠĠĠĠĠ 7 5 Ċ Ġ* ĠĠĠĠĠĠ 9 5 Ġ 6 4 Ċ Ġ* ĠĠĠĠĠĠ 1 7 Ġ 4 7 Ġ 8 2 Ċ Ġ* ĠĠĠĠĠĠ 1 8 Ġ 3 5 Ġ 8 7 Ġ 1 0 Ċ Ġ* ĠĠĠĠĠĠ 2 0 Ġ 0 4 Ġ 8 2 Ġ 4 7 Ġ 6 5 Ċ Ġ* ĠĠĠĠĠĠ 1 9 Ġ 0 1 Ġ 2 3 Ġ 7 5 Ġ 0 3 Ġ 3 4 Ċ Ġ* ĠĠĠĠĠĠ 8 8 Ġ 0 2 Ġ 7 7 Ġ 7 3 Ġ 0 7 Ġ 6 3 Ġ 6 7 Ċ Ġ* ĠĠĠĠĠĠ 9 9 Ġ 6 5 Ġ 0 4 Ġ 2 8 Ġ 0 6 Ġ 1 6 Ġ 7 0 Ġ 9 2 Ċ Ġ* ĠĠĠĠĠĠ 4 1 Ġ 4 1 Ġ 2 6 Ġ 5 6 Ġ 8 3 Ġ 4 0 Ġ 8 0 Ġ 7 0 Ġ 3 3 Ċ Ġ* ĠĠĠĠĠĠ 4 1 Ġ 4 8 Ġ 7 2 Ġ 3 3 Ġ 4 7 Ġ 3 2 Ġ 3 7 Ġ 1 6 Ġ 9 4 Ġ 2 9 Ċ Ġ* ĠĠĠĠĠĠ 5 3 Ġ 7 1 Ġ 4 4 Ġ 6 5 Ġ 2 5 Ġ 4 3 Ġ 9 1 Ġ 5 2 Ġ 9 7 Ġ 5 1 Ġ 1 4 Ċ Ġ* ĠĠĠĠĠĠ 7 0 Ġ 1 1 Ġ 3 3 Ġ 2 8 Ġ 7 7 Ġ 7 3 Ġ 1 7 Ġ 7 8 Ġ 3 9 Ġ 6 8 Ġ 1 7 Ġ 5 7 Ċ Ġ* ĠĠĠĠĠĠ 9 1 Ġ 7 1 Ġ 5 2 Ġ 3 8 Ġ 1 7 Ġ 1 4 Ġ 9 1 Ġ 4 3 Ġ 5 8 Ġ 5 0 Ġ 2 7 Ġ 2 9 Ġ 4 8 Ċ Ġ* ĠĠĠĠĠĠ 6 3 Ġ 6 6 Ġ 0 4 Ġ 6 8 Ġ 8 9 Ġ 5 3 Ġ 6 7 Ġ 3 0 Ġ 7 3 Ġ 1 6 Ġ 6 9 Ġ 8 7 Ġ 4 0 Ġ 3 1 Ċ Ġ* ĠĠĠĠĠĠ 0 4 Ġ 6 2 Ġ 9 8 Ġ 2 7 Ġ 2 3 Ġ 0 9 Ġ 7 0 Ġ 9 8 Ġ 7 3 Ġ 9 3 Ġ 3 8 Ġ 5 3 Ġ 6 0 Ġ 0 4 Ġ 2 3 Ċ Ġ* ĠĠĠĠĠ ĠNOTE : ĠAs Ġthere Ġare Ġonly Ġ 1 6 3 8 4 Ġroutes , Ġit Ġis Ġpossible Ġto Ġsolve Ġthis Ġproblem Ġby Ġtrying Ġevery Ġroute . Ċ Ġ* ĠĠĠĠĠ ĠHowever , ĠProblem Ġ 6 7 , Ġis Ġthe Ġsame Ġchallenge Ġwith Ġa Ġtriangle Ġcontaining Ġone - h undred Ġrows ; Ċ Ġ* ĠĠĠĠĠ Ġit Ġcannot Ġbe Ġsolved Ġby Ġbr ute Ġforce , Ġand Ġrequires Ġa Ġcle ver Ġmethod ! Ġ; o ) Ċ Ġ*/ Ċ const Ġval Ġstr Ġ= Ġ" 7 5 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 9 5 Ġ 6 4 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 1 7 Ġ 4 7 Ġ 8 2 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 1 8 Ġ 3 5 Ġ 8 7 Ġ 1 0 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 2 0 Ġ 0 4 Ġ 8 2 Ġ 4 7 Ġ 6 5 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 1 9 Ġ 0 1 Ġ 2 3 Ġ 7 5 Ġ 0 3 Ġ 3 4 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 8 8 Ġ 0 2 Ġ 7 7 Ġ 7 3 Ġ 0 7 Ġ 6 3 Ġ 6 7 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 9 9 Ġ 6 5 Ġ 0 4 Ġ 2 8 Ġ 0 6 Ġ 1 6 Ġ 7 0 Ġ 9 2 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 4 1 Ġ 4 1 Ġ 2 6 Ġ 5 6 Ġ 8 3 Ġ 4 0 Ġ 8 0 Ġ 7 0 Ġ 3 3 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 4 1 Ġ 4 8 Ġ 7 2 Ġ 3 3 Ġ 4 7 Ġ 3 2 Ġ 3 7 Ġ 1 6 Ġ 9 4 Ġ 2 9 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 5 3 Ġ 7 1 Ġ 4 4 Ġ 6 5 Ġ 2 5 Ġ 4 3 Ġ 9 1 Ġ 5 2 Ġ 9 7 Ġ 5 1 Ġ 1 4 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 7 0 Ġ 1 1 Ġ 3 3 Ġ 2 8 Ġ 7 7 Ġ 7 3 Ġ 1 7 Ġ 7 8 Ġ 3 9 Ġ 6 8 Ġ 1 7 Ġ 5 7 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 9 1 Ġ 7 1 Ġ 5 2 Ġ 3 8 Ġ 1 7 Ġ 1 4 Ġ 9 1 Ġ 4 3 Ġ 5 8 Ġ 5 0 Ġ 2 7 Ġ 2 9 Ġ 4 8 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 6 3 Ġ 6 6 Ġ 0 4 Ġ 6 8 Ġ 8 9 Ġ 5 3 Ġ 6 7 Ġ 3 0 Ġ 7 3 Ġ 1 6 Ġ 6 9 Ġ 8 7 Ġ 4 0 Ġ 3 1 \ n " Ġ+ ĊĠĠĠĠĠĠĠ Ġ" 0 4 Ġ 6 2 Ġ 9 8 Ġ 2 7 Ġ 2 3 Ġ 0 9 Ġ 7 0 Ġ 9 8 Ġ 7 3 Ġ 9 3 Ġ 3 8 Ġ 5 3 Ġ 6 0 Ġ 0 4 Ġ 2 3 " Ċ val Ġrows : ĠList < List < Int >> Ġ= Ġstr . split ("\ n "). map Ġ{ Ġx Ġ-> Ġx . split (" Ġ"). map Ġ{ Ġit . toInt () Ġ} Ġ} Ċ Ċ fun Ġp 1 8 () Ġ{ ĊĠĠĠ Ġprint ( getMax ( 0 , Ġ 0 , Ġ 0 )) Ċ } Ċ Ċ fun ĠgetMax ( sum : ĠInt , Ġi : ĠInt , Ġj : ĠInt ): ĠInt Ġ{ ĊĠĠĠ Ġif Ġ( i Ġ> Ġrows . last Index ) Ġ{ ĊĠĠĠĠĠĠĠ Ġprintln (" Total : Ġ$ sum ") ĊĠĠĠĠĠĠĠ Ġreturn Ġsum ĊĠĠĠ Ġ} ĊĠĠĠ Ġprintln (" -> Ġ${ rows [ i ][ j ]} Ġ[$ i ,$ j ] Ġsum : Ġ${ sum Ġ+ Ġrows [ i ][ j ]} ") ĊĠĠĠ Ġreturn Ġmax Of ( getMax ( sum Ġ+ Ġrows [ i ][ j ], Ġi + 1 , Ġj ), ĠgetMax ( sum Ġ+ Ġrows [ i ][ j ], Ġi + 1 , j + 1 )) Ċ } ĊĊĊĊ