Show problems as
Classic problem #337MediumDynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees

House Robber III

Real-world version: Bonus Pool Without Direct Reports
Tracked in this browser only
Read House Robber III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A firm's reporting lines form a binary chart: every person has at most two direct reports, one recorded on their left and one on their right.

The chart arrives as chart, a level-by-level listing. chart[0] is the chief. After that, every person already listed contributes two entries in turn, their left direct report then their right direct report, with null where that report does not exist. A null contributes nothing further, and null entries at the very end of the listing are left off. Each entry is the discretionary bonus recorded for that person, which is never negative.

The board will pay a selection of these bonuses in one round, under a single rule: if a person is paid, neither of their direct reports may be paid in that round.

Return the largest total the board can pay out.

Examples

Example 1

Input
chart = [0, 1, 7, 10]
Output
17

Pay the person recorded as 7 and the person recorded as 10. Neither is a direct report of the other, and the two bonuses come to 17.

Example 2

Input
chart = [3, 4, 5]
Output
9

The chief's two direct reports hold 4 and 5. Neither reports to the other, so both may be paid in the same round, for 9.

Example 3

Input
chart = [5]
Output
5

The chief is the only person on the chart, and paying them comes to 5.

Constraints

  • The number of people in the chart is in the range [1, 10^4].
  • 0 <= bonus <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_bonus_pool(chart: list[int | None]) -> int:
Java
public int bestBonusPool(Integer[] chart)

More on the same topics