**Problem 67:**

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

374 246 8 593

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and ‘Save Link/Target As…’), a 15K text file containing a triangle with one-hundred rows.

**NOTE:** This is a much more difficult version of Problem 18 (and my attempt). It is not possible to try every route to solve this problem, as there are 2^{99}altogether! If you could check one trillion (10^{12}) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

**Idea:**

Since I already did the work for this on problem 18, I decided to just do what I did for that problem, and sure enough, it worked rather quickly. On my computer, less than a second.

int answer = -1; int[][] tree = EulerUtils.readMatrix("Problem_67.txt"); long start = System.currentTimeMillis(); EulerUtils.SumTreePath path = EulerUtils.treePath(tree,true); long end = System.currentTimeMillis(); System.out.println("Start: "+start+"\tEnd: "+end); answer = path.getSum();