Think about each node as a potential "turning point" of a path. A path through node X might go: left subtree → X → right subtree.
For each node, compute two things:
- The max path sum where this node is the highest point (can include both children).
- The max "gain" this subtree can contribute to a path that continues upward (can include at most one child).
Use post-order traversal. After processing children, compute the max path sum with current node as turning point. Update the global maximum. Return the max gain for the parent's calculation.
If a subtree's gain is negative, don't include it (use 0 instead).