Szerintem a jó algoritmus:
1. Alulról felfelé haladunk a fában, tehát először a legalsó sorban vagyunk.
2. Minden fa pontra kiszámoljuk a maximális összeget az alatta levő két szám alapján. A legalsó sorban, nyilván a szám lesz a maximális összeg. Ezt az összeget és az alatti fa pont indexét letároljuk ehhez a fa ponthoz.
3. Egy sorral feljebb megyünk és folytatjuk a 2. ponttal, amíg el nem fogynak a sorok.
4. A fa csúcsán szerepel a maximális út összege. Fentről lefelé összegyűjtjük az indexeket, ez lesz az út.
A példánál ezen összegeket és indexeket számolja az algoritmus:
(9,0) (2,0) (3, 0)
(13,1) (9,3)
(18,1)
Tehát 18 a max összeg és az (1,1,0) az útvonal, tehát a legfelső elem az első mindig: 5, majd a következő sor első indexű eleme: 4, majd a következő sor első indexű eleme: 9, és mivel 0 van, így kész vagyunk.