You are given a binary tree where each node has an integer value (possibly negative). A path is a sequence of nodes connected by edges. Find the maximum path sum. The path must contain at least one node but does not need to pass through the root.
This is a classic path problem on trees. Every path has a highest node; consider each node as a candidate. Track the global maximum across all possible highest nodes.