An organization's reporting structure is a binary tree. Every employee carries an integer influence score, which may be negative. A chain of command starts at the CEO (the root) and repeatedly moves down to one of the current employee's direct reports (a child), ending at any employee. The chain must start at the root and be contiguous (no gaps).
The authority of a chain is the sum of the influence scores of the employees on it. Report the maximum authority over all chains of command. A chain may consist of the root alone.
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 either an integer influence score or null for a missing child. Children of null nodes are omitted.
A single integer: the maximum authority of any chain of command.
Example 1
Input
3 3 -2 4
Expected
7
Explanation
Chains from the root: just 3 gives 3; 3 then -2 gives 1; 3 then 4 gives 7. The best is 3 + 4 = 7.
Example 2
Input
3 -1 null -2
Expected
-1
Explanation
The root alone gives -1; extending to its only report gives -1 + -2 = -3. The maximum is the root by itself, -1.
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 →