Given a root like structure like this:
9 2 3 8 2 9 4 7 8 5
You can only go from top to bottom, and only once left or right per row. From top to bottom, find the maximum total of these numbers.
The solution for this 4 row deep tree is:
9 + 3 + 9 + 8 = 29.
You will find that by trying every possible route to solve the problem could result in 2^49 variations in a 50 row deep root. If you can check 10^5 results in one second, that would take 178 years to check them all. However, it works for the example above and a few more rows too, but that’s not the solution I’m looking for.
There is an efficient algorithm to solve this, I’m looking for a few seconds of a runtime. Let’s say everything from 2 to 15 seconds will be accepted. I can consider the brute force solution as a 50% success. Using a time machine or Google is not allowed. (although I can’t find the solution in Google)
The structure in the text file is provided without leading spaces:
4 4 7 7 3 4 9 2 0 4 8 5 9 9 3
… and so on.
Download the text file: Tree.txt