Each node of a binary tree holds a profit, which may be negative. A path is any sequence of nodes where each consecutive pair is joined by an edge and no node repeats. The path need not pass through the root, but it must contain at least one node.
Print the largest possible sum of the values on a path.
Constraints
- 1 ≤ number of nodes ≤ 10000
- −1000 ≤ value ≤ 1000
Input and output
- Input
- Line 1: n, the number of tokens. Line 2: the tree in level order — n tokens, each an integer or `null` for a missing child (trailing nulls may be left out).
- Output
- One integer.
Examples
Input 1
3
1 2 3Output
6The path 2 → 1 → 3 sums to 6.
Input 2
7
-10 9 20 null null 15 7Output
42The best path is 15 → 20 → 7 = 42; going up to −10 would only lower it.
Show hints
- For each node, compute the best downward path that starts at it.
- The best path that "bends" at a node uses that node plus the best non-negative downward gains from both children.
Show the explanation
Do one post-order traversal. For each node, gain(node) is the best sum of a path that starts at the node and goes down into at most one child: value + max(0, gain(left), gain(right)). A path that bends at this node can use both sides: value + max(0, gain(left)) + max(0, gain(right)). Update a global best with that, and return gain to the parent. Starting best at the root value (not 0) handles all-negative trees.
Original UniCircle question. Last reviewed 22 Oct 2026.