The two-quantity pattern at full strength

The same idea as the diameter lesson, with one extra decision that makes it much harder.

Why it works

The addition: a branch can be declined

When values can be negative, extending into a subtree can make a path worse. A path is not required to include anything, so the right move is to treat any negative contribution as zero.

Concretely, clamp each child's returned value at zero before using it. A child offering -7 contributes 0 instead, which is the same as not going that way at all.

That single max(child, 0) is the whole difference in difficulty, and it is why the problem is Hard while the diameter is Medium.

All of it happens at one node. Below, a single node is handed whatever its two children reported, with no recursion in sight, so that the two numbers it produces can be compared side by side.

1def consider(value, left_arm, right_arm):2    left = max(left_arm, 0)              # decline a branch that only subtracts3    right = max(right_arm, 0)4    print(f"value {value}, arms {left_arm} and {right_arm}:"5          f" tops out at {value + left + right}, offers {value + max(left, right)}")6 7consider(2, 4, 3)8consider(2, -4, 3)9consider(-3, -1, -1)

Tops out is the candidate answer. Offers is what the parent may extend.

The checklist for this family

Write down what the node returns and what it updates, as two sentences. Decide whether a child's contribution can be declined, and clamp if so. Initialize the running best to something no real answer can beat. Check the all-negative case.

Those four steps solve this problem and every variant of it. The pattern is worth more than the problem.

Predict the output· 5 min

Predict the output: starting the best at zero

The only node in the tree holds -3 and has no children, so the answer must be -3. This shows what the running best becomes under two different starting values. Type the two lines it prints.

Python

1def top_out(value, left_arm, right_arm, running_best):2    """What the running best becomes once this node has been considered."""3    left = max(left_arm, 0)4    right = max(right_arm, 0)5    return max(running_best, value + left + right)6 7print(top_out(-3, 0, 0, 0))8print(top_out(-3, 0, 0, float("-inf")))

Printed output

Problem· 35 min

Binary Tree Maximum Path Sum

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def consider(value, left_arm, right_arm):2 left = max(left_arm, 0) # decline a branch that only subtracts3 right = max(right_arm, 0)4 print(f"value {value}, arms {left_arm} and {right_arm}:"5 f" tops out at {value + left + right}, offers {value + max(left, right)}")6 7consider(2, 4, 3)8consider(2, -4, 3)9consider(-3, -1, -1)

The checklist for this family

Those four steps solve this problem and every variant of it. The pattern is worth more than the problem.

1def top_out(value, left_arm, right_arm, running_best):2 """What the running best becomes once this node has been considered."""3 left = max(left_arm, 0)4 right = max(right_arm, 0)5 return max(running_best, value + left + right)6 7print(top_out(-3, 0, 0, 0))8print(top_out(-3, 0, 0, float("-inf")))