# Project Euler – Maximum path sum (Part 1)

This is what I am currently working on:

I don’t have the solution yet, so this blog post will contain some thoughts that hopefully will at least lead me in the right direction.

# Always pick the highest number?

My first idea was to always pick the highest adjacent number. This is what’s done in the given example: 3 + 7 + 4 + 9.

This would lead to 75 + 95 + 47 + 87 + 82 + 75 + 73 + 28 + 83 + 47 + 43 + 73 + 91 + 67 + 98 = 1064. Unfortunately this is not the correct solution.

Therefore going for the highest number is not the correct strategy.

# Is it a tree?

This looks like a tree. But I have to be careful.

This is not the kind of tree I am looking for, as I could never reach from node “4” to the adjacent node with the same value:

What I need is a tree that looks like the following:

So how to do I create such a structure programmatically?

The problem shows a root node plus 14 additional node levels. This might result in heavy typing which I want to avoid.

# Work from top or bottom?

Once I have a tree, how do I process it? Looks like a call for recursion? Top-down? Bottom-up?

# Sanity check

I know that 1064 is not the correct solution. Therefore the solution must be a larger number. Also it cannot be more than 1313. Most likely the solution is closer to 1064.