Maximum-sum path down a triangle of numbers

Question

We have a triangle of $n$ positive and integer number. we start from top or (head) of this triangle and in each step we are going to adjacent number in next row. goal is finding path of maximum consecutive number.

example: selected number in following figure has length at most $23$.

the best algorithm for finding this path has order of $O(n^2)$.

It's so not very sensible for me how we can find the path (what is the fastest logical way of solving this puzzle)? $$\begin{array} 0&&&(3)\\ &&(7)&&4\\ &2&&(4)&&6\\ 8&&5&&(9)&&3\end{array}$$

Answer 1

The algorithm to find the largest-sum path in $O(n^2)$ time is as follows:

• for each number in the second-last row $c$, look at the two numbers below it, $l$ and $r$. Replace $c$ with $c+l$ or $c+r$, whichever is larger, and note the direction that must be followed to achieve the larger value ($L$ or $R$ correspondingly)
• recurse in the smaller triangle, prepending to the strings of $L$ and $R$ from previous steps
• eventually you are left with one number, which is the largest possible sum, and the path to achieve it

$$\begin{array} 0&&&3\\ &&7&&4\\ &2&&4&&6\\ 8&&5&&9&&3\end{array}\to \begin{array} 0&&3\\ &7&&4\\ 10L&&13R&&15L\end{array}$$ $$\begin{array} 0&&3\\ &7&&4\\ 10L&&13R&&15L\end{array}\to \begin{array} 0&3\\ 20RR&&19RL\end{array}\to23LRR$$ This works because we are going to pass through the second-last row regardless of what path we take, and in that row the choice we want to make (to maximise the sum) is clear. It is a kind of dynamic programming.