Question

Se dau n(n+1)/2 numere naturale aranjate intr-un triunghi format din elementele de sub si de pe diagonala unei matrici patratice de ordin n.
Se calculeaza sume pornind din elementul de pe prima linie prin deplasari in vecinii de sub si din dreapta. Gasiti suma maxima care se poate calcula astfel si care sunt valorile din care se obtine suma maxima

Exemplu:
n=4
2
3 5
6 3 4
5 6 1 4

suma maxima este 17
si se obtine din valorile {2, 3, 6, 6}

Nu vreau sa imi faceti problema, vreau doar sa imi explicati exemplul in detaliu (cum de a trecut prin 2,3,6,6 incat sa faca suma 17). Multumesc

Answer 1

Explicație:

Este ceruta suma maxima deplasandu-ne in jos si la dreapta, asta inseamna ca putem forma sume cu valorile:

2 3 6 5

2 3 6 6

2 3 6 1

2 3 6 4

2 3 3 6

2 3 3 1 si asa mai departe, ultima pereche fiind 2 5 4 4. Sper ca ai inteles metoda.

Si din aceste perechi de valori suma maxima este formata din cea cu valorile 2 3 6 6.

2+3+6+6=17

Daca tot nu ai inteles scrie-mi si iti voi explica mai in detaliu.