A mining region is modeled as a binary tree; each node has an integer ore yield, which may be negative (a node can cost more to clear than it returns). For any node, the block yield is the sum of ore yields of that node and all of its descendants (its subtree). Report the maximum block yield over all nodes.
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer yield or null for a missing child. Children of null nodes are omitted.
A single integer: the maximum block yield.
Example 1
Input
3 1 -2 3
Expected
3
Explanation
Subtree sums: left leaf -2, right leaf 3, whole tree 1 + (-2) + 3 = 2. The largest is 3 (the right leaf).
Example 2
Input
3 -5 -3 -8
Expected
-3
Explanation
All yields are negative. Subtree sums are -3, -8, and -16. The largest, least-negative value is -3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →