The best repeater run

A signal run through a relay network can climb towards the headend for a while and then turn back down another branch. It turns at most once, and that is the whole problem.

The problem

A broadcaster's relay network hangs off one headend site. Each site feeds at most two sites below it, and every site is reached from the headend by exactly one chain of hops. Each site has a gain in decibels: an amplifier adds, a lossy splitter subtracts, so a gain can be negative.

A run is any chain of sites joined by hops that visits no site twice. It may sit inside one branch, or climb from a site up to some common site and back down another branch. Its total is the sum of the gains of the sites on it. A run holds at least one site.

Report the largest total any run achieves.

Input. sites — the network in level order from the headend, None where a site feeds nothing on that side. Gains may be negative.

Output. One integer: the largest total gain of any run.

Example.

sites = [4, 8, 6]   ->  18

The run 8 -> 4 -> 6 climbs from the left site to the headend and back down the right: 8 + 4 + 6 = 18.

A second example, where the best run never reaches the headend:

sites = [-1, -2, 15, None, None, 7, 8]   ->  30

Site 15 feeds 7 and 8. The run 7 -> 15 -> 8 totals 30. Climbing further costs -1 and then -2, so the run stops where climbing stops paying. When every gain is negative, as in [-5, -2, -9], the answer is the least bad single site: -2.

Constraints.

• 1 <= number of sites <= 3 x 10^4
• -10^3 <= gain <= 10^3
• The network may be one long chain

Hints

Approach

Brute force

Take every pair of sites and add the gains along the chain between them. There are about n^2 / 2 pairs and each chain costs up to its length: with 3 x 10^4 sites that is 4 x 10^8 pairs before any addition.

The insight

Every run turns at exactly one site, so ask each site for the best run turning there, and let it hand its parent only the best one-sided descent.

Those are two different numbers and keeping them apart is the entire trick. The turn at a site uses both branches, gain + left + right, and stops — no parent can extend it without visiting the site twice. What the parent can use is gain + max(left, right): it enters from above and leaves down one side.

Both branch figures are clamped at zero: a branch whose best descent is negative is one the run declines to enter, and it may, because a run can start anywhere.

Algorithm

1. Build the network and set best = -infinity.
2. Walk postorder. An absent site contributes 0.
3. At a site, take left = max(descend(left), 0) and the same on the right.
4. Record best = max(best, gain + left + right) — the run that turns here.
5. Return gain + max(left, right) — what a parent can extend.
6. After the walk, best is the answer.

Complexity

Time O(n) — one visit per site, constant work at each. Space O(h) for the recursion stack: about 15 frames on a balanced network, but 3 x 10^4 on a chain, which is past Python's default limit and has to be raised.

Solution

"""The best repeater run — one postorder sweep, recording the bend, returning the descent."""

import sys
from collections import deque

sys.setrecursionlimit(40000)   # a network with no forks is one frame per site


class Site:
    __slots__ = ("gain", "left", "right")

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


def build(plan):
    """Level-order network map, None where a site feeds nothing on that side."""
    if not plan or plan[0] is None:
        return None
    root = Site(plan[0])
    queue = deque([root])
    i = 1
    while queue and i < len(plan):
        node = queue.popleft()
        if i < len(plan):
            gain = plan[i]
            i += 1
            if gain is not None:
                node.left = Site(gain)
                queue.append(node.left)
        if i < len(plan):
            gain = plan[i]
            i += 1
            if gain is not None:
                node.right = Site(gain)
                queue.append(node.right)
    return root


def solve(plan):
    root = build(plan)
    best = float("-inf")            # a run holds at least one site, so 0 is not the floor

    def descend(node):
        """Returns the best run that starts at `node` and only goes downhill."""
        nonlocal best
        if node is None:
            return 0
        left = max(descend(node.left), 0)     # a branch with a negative total is skipped
        right = max(descend(node.right), 0)
        best = max(best, node.gain + left + right)   # the run bends here: both sides count
        return node.gain + max(left, right)          # the parent can only take one side

    descend(root)
    return best

TESTS = [
    (([4, 8, 6],), 18),
    (([-1, -2, 15, None, None, 7, 8],), 30),
    (([10, -30, 5],), 15),
    (([-5, -2, -9],), -2),
    (([-4],), -4),
    (([2, 9, 3, None, None, 1, 6],), 20),
    (([-7, 12, 20, None, None, 5, 3],), 30),
]

Pitfalls

• Returning gain + left + right upward. The parent then builds a chain that goes down into a site, back up, and down its other side. On [2, 9, 3, None, None, 1, 6] it reports 21, counting site 3 twice; the real best is 20.
• Starting best at 0. On an all-negative network it returns 0, which is not a run — no chain of sites sums to it. Start at negative infinity.
• Dropping the clamp. On [10, -30, 5] the unclamped walk carries the -30 branch into the total at the headend and reports 5, when the run 10 -> 5 gives 15.

Variants

• A run with exactly the vertical — a path question with no turn allowed, which is why one number carried down does it.
• The bracket, first round first — the same single visit per node, arranged as a level sweep instead of a postorder.