A vault network is a binary tree; each vault holds a non-negative integer amount of loot. A silent alarm links every vault to its direct parent, so you may not rob a vault and its immediate parent on the same night. Choose any set of vaults that contains no parent-child pair, and maximize the total loot taken.
Report the maximum total loot.
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 a non-negative integer loot amount or null for a missing child. Children of null nodes are omitted.
A single integer: the maximum total loot with no parent-child pair chosen.
Example 1
Input
7 3 2 3 null 3 null 1
Expected
7
Explanation
Take the root (3) plus the two grandchildren (3 and 1), which are not adjacent to the root; that totals 7. Any alternative that includes a child of the root does worse.
Example 2
Input
4 2 1 3 4
Expected
7
Explanation
Taking the leaf 4 (under node 1) and the leaf 3 avoids every parent-child clash and totals 7, which beats taking the root plus node 3 (5) or other choices.
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 →