Triangle Max Path Sum
Maximum sum from top of a 10-row number triangle to the bottom row, moving down-left or down-right at each step.
You’re descending a 10-level carnival pyramid. Each booth pays out the dollar amount printed in its cell. Starting at the top booth (row 1), at each step you walk to one of the two booths directly below — straight down (same column) or down-and-right (next column). You collect the payout at every booth you visit, including the top and the one in row 10.
A1:J10 shows the payout layout, flush-left in a 10×10 range (cells above the
diagonal are empty). Return the maximum total payout of any descent from
row 1 to row 10.
There are 2⁹ = 512 distinct paths. Brute-forcing them by hand is infeasible — the formula has to do the work.
Input
Range A1:J10
| A | B | C | D | E | F | G | H | I | J | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 41 | |||||||||
| 2 | 8 | 2 | ||||||||
| 3 | 48 | 18 | 16 | |||||||
| 4 | 15 | 9 | 48 | 7 | ||||||
| 5 | 44 | 48 | 35 | 6 | 38 | |||||
| 6 | 28 | 3 | 2 | 6 | 14 | 15 | ||||
| 7 | 33 | 39 | 2 | 36 | 13 | 46 | 42 | |||
| 8 | 45 | 35 | 27 | 15 | 29 | 38 | 18 | 1 | ||
| 9 | 49 | 11 | 45 | 28 | 22 | 18 | 10 | 14 | 49 | |
| 10 | 22 | 7 | 6 | 25 | 7 | 23 | 23 | 39 | 17 | 3 |
Hint
Branching recursion: at each cell, value plus MAX of two recursive calls — one straight down, one down-and-right. Base case: row past the last.
Solution
=LET(
tbl, A1:J10,
fx, LAMBDA(me, ro, co,
IF(ro > ROWS(tbl),
0,
INDEX(tbl, ro, co) + MAX(me(me, ro+1, co), me(me, ro+1, co+1))
)
),
fx(fx, 1, 1)
)