One struck reading

A wind tunnel logs a pressure deviation every tenth of a second. One tap on the rig is known to be faulty, so the report is allowed to strike one reading — and that changes which stretch is best.

The problem

A run through the tunnel produces trace, a list of pressure deviations in pascals, positive above the reference and negative below. An engineer reports the strongest stretch: a contiguous run of readings, scored by its total.

Because one pressure tap is faulty, the report may strike out at most one reading from inside the chosen stretch. The readings on either side of a struck one still count as a single stretch — striking a reading closes the gap rather than splitting the run in two. Whatever is struck, the stretch must still contain at least one kept reading, so a one-reading stretch cannot be emptied.

Report the largest total achievable.

Input. trace — a non-empty list of integers, the pressure deviations in order.

Output. The largest total of a contiguous stretch with at most one reading struck out.

Example.

trace = [4, -1, -7, 5, 2]   ->  10

Strike the -7 and the whole run scores 4 - 1 + 5 + 2 = 10. With nothing struck the best stretch is [5, 2], worth 7; striking the -1 instead leaves 4 - 7 + 5 + 2 = 4.

A second example, where nothing can be struck usefully:

trace = [-3, -6, -2, -8]   ->  -2

Every reading is negative, so the best stretch is the single -2. Striking it would leave an empty stretch, which the report does not allow, and an empty stretch is not worth 0.

Constraints.

• 1 <= len(trace) <= 10^5
• -10^4 <= trace[i] <= 10^4

Hints

Approach

Brute force

Take every start, every end, and every reading in between as the candidate to strike, summing each time. With prefix sums that is one subtraction per (start, end, struck) triple, about n^3 / 6 of them — 1.6 * 10^14 at n = 10^5, and even the O(n^2) version that only tries the smallest reading in each window is 10^10.

The insight

A stretch ending at reading i is described completely by one bit — whether the strike has been used — so two running totals are enough, and each is built from the pair at i - 1.

Call them kept and struck. kept extends the previous unbroken stretch or restarts at this reading, exactly as an ordinary best-stretch scan does. struck is the larger of two histories: a stretch that already spent its strike and now absorbs this reading, or a stretch that ended at i - 1 with the strike in hand, with this reading thrown away. Nothing else about the past can affect the future, which is the property that makes two numbers sufficient.

The base case is the awkward part. At the first reading, kept is that reading and struck has no legal value at all — striking it would empty the stretch — so it starts as negative infinity, not 0.

Algorithm

1. Set kept to the first reading, struck to negative infinity, and best to the first reading.
2. For each later reading x, compute the new struck first, as max(struck + x, kept).
3. Then compute the new kept as max(kept + x, x).
4. Update best with both new values.
5. Return best.

Complexity

Time O(n) — one pass, a constant number of comparisons per reading. Space O(1); three numbers, whatever the trace length.

Solution

"""One struck reading — best stretch with at most one reading removed."""

IMPOSSIBLE = float("-inf")


def solve(trace):
    # Invariant after reading i:
    #   kept   = best stretch ending at i with the strike still in hand
    #   struck = best stretch ending at i with the strike already spent
    # struck starts as IMPOSSIBLE because striking the only reading would leave
    # an empty stretch, which is not a legal report.
    kept = trace[0]
    struck = IMPOSSIBLE
    best = trace[0]
    for x in trace[1:]:
        # struck reads the OLD kept: this reading is the one being thrown away.
        struck = max(struck + x, kept)
        kept = max(kept + x, x)
        best = max(best, kept, struck)
    return best

TESTS = [
    (([4, -1, -7, 5, 2],), 10),
    (([-3, -6, -2, -8],), -2),   # all negative: the strike cannot empty the stretch
    (([8, -1, -30],), 8),        # best stretch does not reach the end
    (([6, 3],), 9),
    (([-5],), -5),               # single reading, strike unusable
    (([2, -1, 2, -1, 2],), 5),
    (([4, 4, 4],), 12),          # all equal: striking one only loses value
]

Pitfalls

• Starting struck at 0. That says "a stretch with the strike used and no readings kept is worth 0", which is the empty stretch the brief forbids. The all-negative trace [-3, -6, -2, -8] then reports 0 instead of -2.
• Updating kept before struck. The new struck would read a kept that already contains this reading, so the strike is always spent on the reading just added and buys nothing. The first example comes back as 7.
• Reading the answer off the last index. The best stretch need not reach the end: on [8, -1, -30] the final pair is 7, while the answer is the 8 alone. Track a running maximum over every position.

Variants

• Motif in the weave — another scan that carries several states at once, counting instead of maximising.
• Intervals and matrices — where the "what does the state have to remember" question is worked through.