The searchable section

A catalogue that was once ordered has been re-filed in places and no longer is. You want the heaviest block of it that still obeys the rule.

The problem

A seed vault keeps batches in drawers. Each drawer carries a viability score, an integer that goes negative once a batch has degraded past use. The drawers are wired into a binary tree: each has a left slot and a right slot, either empty.

The vault was built so a curator could find a batch by score: for any drawer, every score in the block off its left slot is strictly smaller, and every score off its right slot is strictly larger. Re-filing has broken that in places.

A section is one drawer with everything below it, and it is searchable when the ordering rule holds at every drawer inside it. Report the largest total score over all searchable sections. Lifting nothing out is allowed, so if no searchable section has a positive total the answer is 0.

Input. catalogue — the tree level by level, None for an empty slot. An empty slot lists no children.

Output. The largest total score of any searchable section.

Example.

catalogue = [5, 9, 3, None, None, 2, 7]   ->  12

Drawer 5 holds the larger 9 in its left slot, so the full catalogue fails. The section under 3 — 2 on the left, 7 on the right — is searchable and totals 12. The lone 9 is a searchable section too, but worth only 9.

A second example, where a degraded batch is still worth keeping:

catalogue = [10, -5, 20, None, None, 15, 30]   ->  70

This whole catalogue is searchable, and totals 70. Dropping the -5 for just the section under 20 gives 65, so carrying the degraded drawer pays.

Constraints.

• 0 <= number of drawers <= 4 * 10^4
• -10^4 <= score <= 10^4
• Scores may repeat across the catalogue; a section holding two equal scores is not searchable.

Hints

Approach

Brute force

Take each drawer in turn, walk its section in order, confirm the scores come out increasing, and add them up. Sections nest, so a catalogue shaped like a spine costs about n²/2 drawer visits — 8 x 10⁸ at the top of the range.

The insight

A drawer can rule on its own section in constant time once each child reports four facts: searchable or not, the smallest score below it, the largest, and the total.

The rule is then local: the section is searchable exactly when both children's blocks are, the largest score on the left is below the drawer, and the smallest on the right is above it. The report is closed under that step — a drawer's four facts follow from its children's and its own score — so one bottom-up pass fills every drawer at O(1) each.

Algorithm

1. Rebuild the tree from the level-order list.
2. Walk it in postorder on an explicit stack, so both children settle before their parent — a 40,000-drawer spine overflows Python's recursion limit.
3. For a drawer scoring s, start from (True, s, s, s).
4. A left child must be searchable with high < s; take its low, add its total.
5. A right child must be searchable with low > s; take its high, add its total.
6. When a section is searchable, test its total against the best, which starts at 0.

Complexity

Time O(n) — one visit per drawer, constant work each. Space O(n) for the reports and the stack.

Solution

"""The searchable section — postorder tree DP returning (ordered, low, high, total)."""

from collections import deque


class Drawer:
    """One drawer of the catalogue: a viability score and two child slots."""

    __slots__ = ("score", "left", "right")

    def __init__(self, score):
        self.score = score
        self.left = None
        self.right = None


def build(level_order):
    """Rebuild the catalogue from its compact level-order form."""
    if not level_order or level_order[0] is None:
        return None
    root = Drawer(level_order[0])
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        # invariant: only real drawers are queued, so a gap never claims child slots
        node = queue.popleft()
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.left = Drawer(value)
                queue.append(node.left)
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.right = Drawer(value)
                queue.append(node.right)
    return root


def solve(catalogue):
    root = build(catalogue)
    if root is None:
        return 0

    # A drawer's verdict is (ordered, low, high, total) for the section below it.
    # Lifting nothing is allowed, so the answer never drops under 0.
    verdict = {}
    best = 0
    stack = [(root, False)]
    while stack:
        node, children_done = stack.pop()
        if not children_done:
            stack.append((node, True))
            if node.left is not None:
                stack.append((node.left, False))
            if node.right is not None:
                stack.append((node.right, False))
            continue
        # invariant: both children are already in `verdict` when we reach here,
        # because a parent is only re-pushed underneath its children
        ordered, low, high, total = True, node.score, node.score, node.score
        if node.left is not None:
            child = verdict[id(node.left)]
            ordered = ordered and child[0] and child[2] < node.score
            low = min(low, child[1])
            total += child[3]
        if node.right is not None:
            child = verdict[id(node.right)]
            ordered = ordered and child[0] and child[1] > node.score
            high = max(high, child[2])
            total += child[3]
        verdict[id(node)] = (ordered, low, high, total)
        if ordered and total > best:
            best = total
    return best

TESTS = [
    (([5, 9, 3, None, None, 2, 7],), 12),
    (([10, 25, 20, None, None, 15, 30],), 65),
    (([8, 4, 12, 2, 6, 10, 20],), 62),
    (([10, -5, 20, None, None, 15, 30],), 70),
    (([-4, -6, -2],), 0),
    (([4, 4, 6],), 6),
    (([10, 5, 20, None, 12],), 20),
    (([],), 0),
    (([7],), 7),
    (([-9],), 0),
]

Pitfalls

• Comparing a drawer only against its two children. On [10, 5, 20, None, 12] every parent-child pair is in order, yet 12 sits in the left block of 10. That check reports 47; the answer is 20.
• Starting the best total below zero. Seed it at negative infinity and an all-degraded catalogue like [-4, -6, -2] answers -12. Lifting nothing is legal, so the floor is 0.
• Letting scores tie. Relax the bounds to <= and >= and [4, 4, 6] comes back as 14, counting a duplicate as ordered. Both bounds are strict.

Variants

• Tree, digit and bitmask DP — the general shape: a postorder tuple each parent folds into its own.
• Two crews, one siding — a DP down a line, carrying state forward instead of upward.