Loudest run on the board

A pedalboard multiplies. Two phase-inverting pedals in a row cancel, which means the worst run so far is one negative pedal away from being the best.

The problem

Pedals sit in a fixed order on a board, wired left to right. Pedal i has an integer gain gains[i]: the signal leaving it is the signal entering it times that number. A negative gain means the pedal also flips the phase. A gain of zero is a kill switch — anything downstream of it in the same run is silence.

The patch cable enters the chain at one pedal and leaves at another, so the pedals actually in circuit are always a contiguous run, and at least one pedal is in circuit. The overall gain of a run is the product of its pedals' gains. Report the largest overall gain any run can produce.

Input. gains — a list of integers, in board order.

Output. The largest product over all contiguous runs of at least one pedal.

Example.

gains = [3, -1, -4, 2]   ->  24

The whole board: 3 x -1 x -4 x 2 = 24. The two inverting pedals cancel each other, so a run that looks bad in the middle finishes on top.

A second example, where the best run does not touch the loudest pedal:

gains = [5, -2, 0, -3, -6]   ->  18

The kill switch cuts the board in two. On the left the best is 5; on the right, -3 x -6 = 18.

Constraints.

• 1 <= len(gains) <= 2 * 10^4
• -10 <= gains[i] <= 10
• The gain of any run fits in a signed 32-bit integer

Hints

Approach

Brute force

Take every start, extend to every end, multiply as you go. That is n * (n + 1) / 2 runs — about 2 x 10^8 multiplications at the top of the range, and the arithmetic is not the cheap kind.

The insight

Multiplying by a negative number turns the smallest product into the largest, so carry the worst run ending here as well as the best one.

Multiplication by a fixed value is monotone when that value is positive and order-reversing when it is negative. Either way the extreme products of the new set come only from the extreme products of the old set — everything between them stays between them. Two numbers per pedal are therefore enough, and the interior runs never need to be looked at.

Algorithm

1. Set high, low and best all to gains[0].
2. For each later gain g: if g < 0, swap high and low.
3. Set high = max(g, high * g) and low = min(g, low * g), both from the pair as it stood after the swap.
4. Update best with high.
5. Return best.

Complexity

Time O(n) — one pass, a constant number of multiplications per pedal. Space O(1) — three integers, whatever the board's length.

Solution

"""Loudest run on the board — carry the best and the worst product ending at each pedal."""


def solve(gains):
    """Largest overall gain of any contiguous run of pedals in the chain."""
    best = high = low = gains[0]
    for gain in gains[1:]:
        # Invariant: high and low are the largest and smallest products of any
        # run that ends at the previous pedal. A negative pedal swaps their
        # roles, which is why the worst run has to be carried along at all.
        if gain < 0:
            high, low = low, high
        high = max(gain, high * gain)
        low = min(gain, low * gain)
        best = max(best, high)
    return best

TESTS = [
    (([3, -1, -4, 2],), 24),
    (([5, -2, 0, -3, -6],), 18),
    (([2, -1, 3, 0, 4],), 4),
    (([-5],), -5),
    (([0, 0],), 0),
    (([-2, -3, 0, -2, -40],), 80),
    (([7],), 7),
    (([-1, -1, -1],), 1),
    (([-3, -3, -3],), 9),
]

Pitfalls

• Computing low from the freshly updated high. Both must come from the previous pair. Read the new one and [-3, -3, -3] reports 81, a product no run on the board can make; the answer is 9.
• Dropping the "start fresh at g" option. After a kill switch both carried numbers are zero and stay zero, so [5, -2, 0, -3, -6] returns 5 instead of 18.
• Seeding high, low and best with 1 or 0 instead of gains[0]. A board of one inverting pedal, [-5], then returns 1 or 0 — but the cable has to be patched in somewhere, so -5 is the honest answer.

Variants

• Posts on an even grade — the same one-pass carry, counting runs instead of scoring them.
• The period in a sighting ledger — drops the contiguity, and the state grows by a whole dimension.