Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of adjacent nodes with no repeats; it need not pass through the root. Given the root of a tree whose values may be negative, return the maximum sum of values along any path.
- 1 ≤ number of nodes ≤ 3 · 10^4
- -1000 ≤ node value ≤ 1000
- Values can be negative, so a branch may be worth dropping (clamp at 0)
- The best path through a node = node + best left arm + best right arm
- A node returns only the best single arm to its parent — Kadane on a tree
The best subarray ending at index i is either the element alone or the element appended to the best subarray ending at i - 1; a negative running sum is never worth carrying. This is a one-variable DP over "best ending here", which generalizes to product subarrays (track min and max) and stock problems.
Do a post-order traversal where each node returns the best downward path starting at it: value + max(0, leftGain, rightGain). Ignoring a negative arm is the same choice Kadane makes when it resets a negative running sum. While at the node, also evaluate the path that bends through it — value + max(0, leftGain) + max(0, rightGain) — and track the global maximum. The global maximum after the traversal is the answer.
- Enumerating all pairs of nodes with LCA-based sums is O(n^2). There is no simpler correct approach; the key is separating "best arm" from "best bent path".