Binary Tree Maximum Path Sum
Signals to notice
Brute force first
Check every possible path. For each node, compute the best path through it independently. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
DFS returning max single-path sum. At each node, compute the through-path (left + node + right) and update global max. Return the best one-sided path (node + max(left, right)) for the parent to use. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
What must stay true
At each node, the maximum path THROUGH it is left_gain + node.val + right_gain (where gains are clamped to 0). But the value returned to the parent is node.val + max(left_gain, right_gain) — you can only extend in one direction upward. As long as that statement keeps holding, you can trust the steps built on top of it.
Easy way to go wrong
Returning the through-path value to the parent — a path can't fork. You must return the best single-sided path. The through-path is only used to update the global maximum. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.