Citadel Interview Question

Find the maximum sum path in a pyramid.

Interview Answer

Anonymous

Apr 28, 2017

You can start from the bottom of the n-level pyramid, decompose the last two rows into n-1 2-level pyramids, find the path for each 2-level pyramids. Replace the second last row with the sum of the numbers on each path. Now you have a n-1-level pyramid and paths. Then repeat these steps n-1 times you will get the maximum path.

1