Loading...
Loading...
Loading...
Kabir plays a heist game on his phone. The houses of a town are joined by roads that form a tree: there is one house at the top, and every house has at most two houses joined below it. Each house holds some coins.
The houses that are joined directly by a road share an alarm. If the thief takes coins from two such houses on the same night, the alarm rings and the game ends.
Print the most coins the thief can collect in one night without ringing the alarm. A town with no houses gives 0.
N for no house. Children are listed only for real houses, and N tokens at the end of the line may be left out. For example, 3 2 3 N 3 N 1 N N N N is house 3 at the top with children 2 and 3. House 2 has only a right child 3, and the other house 3 has only a right child 1. The last two houses have no children. An empty town is the single token N.long.Example 1
Input
3 2 3 N 3 N 1 N N N N
Output
7
Take the top house 3 and the two lowest houses 3 and 1. None of them share a road, so the total is 7.
Example 2
Input
3 4 5 1 3 N 1 N N N N N N
Output
9
Take 4 and 5, the two children of the top house. The total is 9, which beats 3 + 1 + 3 + 1 = 8.
Try the problem first. Open one hint at a time.
For every house, work out two answers for the part of the tree below it: the best total if this house is taken, and the best total if it is skipped.
If the house is taken, its children must be skipped: take = value + skip(left) + skip(right).
If the house is skipped, each child is free to be taken or skipped: skip = max(take, skip) of the left child + max(take, skip) of the right child.
Compute the children before the parent with one recursive method that returns both numbers. A missing child gives 0 and 0. The answer is the larger of the two numbers for the top house.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor