Show problems as
Classic problem #124HardDynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees

Binary Tree Maximum Path Sum

Real-world version: Best Chamber Run
Tracked in this browser only
Read Binary Tree Maximum Path Sum on LeetCode(opens in a new tab)

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

Learn the pattern firstPath Sum & Root to Leaf · Binary Trees & BST, animated step by step

A survey crew has mapped a cave system that branches downward. Every chamber carries one signed pressure figure in millibars: positive where air is pushed out, negative where air is drawn in.

The map arrives as chambers, a listing of the cave one depth at a time, left to right. Slot 0 holds the mouth chamber. Each chamber that appears in the listing claims the next two free slots for its downhill passages, the left one first and the right one second. A slot holding null means no chamber hangs there, and such a slot claims no slots of its own. Slots holding null at the very end of the listing may be left off.

A run visits one or more chambers, steps only between chambers joined by a single passage, and never revisits a chamber. It may begin and end at any chamber, and it need not touch the mouth. The yield of a run is the total of the pressure figures of the chambers it visits.

Return the largest yield any run can reach. At least one chamber is always mapped, so a run always exists, and the answer can be negative when every chamber draws air in.

Examples

Example 1

Input
chambers = [5, -20, 6]
Output
11

Starting at the right chamber, stepping up to the mouth and stopping there collects 6 + 5. Extending into the left chamber would cost 20, so the run stops.

Example 2

Input
chambers = [-9, 2, 8, null, null, 11, 4]
Output
23

The run 11, 8, 4 stays inside the right branch and never pays for the mouth chamber.

Example 3

Input
chambers = [-7]
Output
-7

The only run available is the mouth chamber on its own, so its own figure is the answer.

Constraints

  • 1 <= number of mapped chambers <= 3 * 10^4
  • -1000 <= chamber pressure <= 1000
  • chambers[0] is not null
  • chambers is a valid depth-by-depth listing: no slots follow a null slot's position

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_chamber_run(chambers: list[int | None]) -> int:
Java
public int bestChamberRun(Integer[] chambers)

More on the same topics