Trees, Graphs
A good realization is that if a node at has two parents, it can look at the parents to decide which parent would have been more valuable to have traveled through.
We can keep track of, on each node, the “best score to have reached this node”, always choosing the better-parent and using it’s best score, plus that parent’s own data. Then, we just need to additionally keep track of the best score we found by the end of the list.
We can do this without having to traverse multiple paths, but just by visiting each node, and looking at it’s parent’s nodes.
def maxpath(nodes):
"""Given list of nodes in triangle, return high-scoring path."""
# START SOLUTION
# Best score we've seen so far
best = 0
for n in nodes:
if not n.parents:
# For the root, it has no best-path
n.best = n.value
else:
# Take best score of your higher parent and add this value
n.best = n.value + max(p.best for p in n.parents)
# Update best-we've-seen
best = max(n.best, best)
return best