Maximum Sum BST in Binary Tree
Real-world version: The Heaviest Sorted Section of a RigThe statement here is our own: the same inputs, outputs and technique.
A cargo rig is given as the flat list rig. It hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty.
A flat list is read level by level: its first entry is the top joint's load, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own.
A section is one joint together with everything hanging below it. A section is sorted when, for every joint in it, every load in that joint's first slot and below is strictly less than the joint's own load, and every load in its second slot and below is strictly greater.
Return the largest total load any sorted section carries. A section holding no joints at all counts as sorted and carries nothing, so the answer never falls below 0.
Examples
Example 1
- Input
- rig = [5, 3, 8, 2, 4, 7, 9]
- Output
- 38
The whole rig is sorted: everything under 5's first slot is below it and everything under its second slot is above, and the same holds at 3 and at 8. So the answer is every load added together.
Example 2
- Input
- rig = [10, 5, 15, null, null, 6, 20]
- Output
- 41
The whole rig is not sorted, since the 6 hangs under 10's second slot yet is smaller than 10. The section headed by 15 is sorted, carrying 6, 15 and 20, which is heavier than the section headed by 5 on its own.
Example 3
- Input
- rig = [-1]
- Output
- 0
The only section carrying anything carries a negative load, so the empty section, carrying nothing at all, is the heavier one.
Constraints
- 1 <= rig.length <= 120000
- The rig holds between 1 and 4 * 10^4 joints.
- -40000 <= rig[i] <= 40000
- The first entry of the list is not null.
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.
def max_sum_b_s_t(rig: list) -> int:public int maxSumBST(Integer[] rig)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 17 test cases: 17 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's