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.
Input format
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.
Output format
A single integer: the maximum authority of any chain of command.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each influence score is between -1000000 and 1000000.