Recursion and Trees
The two-quantity pattern at full strength
The same idea as the diameter lesson, with one extra decision that makes it much harder.
Key idea
Start from what you already have
The diameter lesson established two sentences. What a node returns is the best thing that can continue upward through one child. What a node updates is the best answer where this node is the top of the path.
Everything about the hardest problem in this unit follows from those two sentences plus one addition.
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.
Gotcha
The running best cannot start at zero
If every value in the tree is negative, the answer is the least negative single node. Starting the running best at 0 would return 0, which is not a path in the tree at all.
Start it at negative infinity. The clamping of children at zero is correct and separate: declining a branch is allowed, but the node itself must always be included in its own path.
The third line above is the case that catches this. A solution that starts the running best at zero handles every tree with a positive answer and fails on any tree that is entirely negative.
Tip
The answer often skips the root
Take a root of -10 whose left child is 9 and whose right child is 20 with children 15 and 7. The best path is 15, 20, 7, which sums to 42 and never touches the root at all. Going through the root would mean 9 plus -10 plus 20, which is far worse.
The two-quantity split is what allows an answer that excludes the root to be found at all. A recursion that only returned values upward could never report it, which is worth remembering as the reason the split exists rather than as a rule to follow.
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: 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.
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.