The hive scale

A hive sits on a scale that logs one number a night: the grams the colony gained or lost that day. The beekeeper wants the best unbroken stretch of the season.

The problem

Each entry in the log is the net change in hive weight for one day — positive while nectar is coming in, negative when the bees eat more stores than they collect. Rain, a cold snap or a robbing day shows up as a large negative.

The beekeeper is choosing which stretch of the season to repeat next year, so they want the largest total gain over one unbroken run of days. The run must contain at least one day; you cannot skip a bad day in the middle of a run and keep both sides, because a stretch is a stretch.

Input. deltas — a non-empty list of integers, the net weight change in grams for each day, in order.

Output. The largest total over any contiguous run of one or more days.

Example.

deltas = [40, -25, 60, -90, 55, 30, -20, 15]   ->  85

The last four days total 80, and the first three total 75, but days 5 and 6 alone total 85. Extending them with -20, 15 only loses 5 g.

A second example, where every day is a loss:

deltas = [-12, -3, -40]   ->  -3

The run must be non-empty, so the answer is the least bad single day, not zero.

Constraints.

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

Hints

Approach

Brute force

Take every start and every end, and add up the days between: about n²/2 runs, each costing up to n additions — 10¹⁵ operations at the top of the constraints. Prefix sums cut the inner add, leaving n²/2 ≈ 5·10⁹ pairs, still far too many.

The insight

The best run ending at today is either today alone or the best run ending yesterday plus today — so one number, carried forward, replaces the whole search over start days.

Every run ending at day i has a start, and dropping day i from it leaves a run ending at day i-1. So the best run ending at i is deltas[i] added to the best run ending at i-1, unless that total is worse than starting fresh at i. The choice depends on nothing but that one running number, which is why the scan is linear: n states, constant work each.

Algorithm

1. Set best_here and best_anywhere to deltas[0].
2. For each later day, set best_here = max(delta, best_here + delta).
3. Update best_anywhere = max(best_anywhere, best_here).
4. Return best_anywhere.

Complexity

Time O(n) — one pass, two comparisons a day. Space O(1); the two running numbers replace the whole table.

Solution

"""The hive scale — best contiguous run carried in one rolling variable."""


def solve(deltas):
    # best_here: the largest total of any run that ends on the current day.
    # It is the only thing the next day needs to know about every earlier day.
    best_here = best_anywhere = deltas[0]
    for delta in deltas[1:]:
        best_here = max(delta, best_here + delta)   # start fresh, or extend
        best_anywhere = max(best_anywhere, best_here)
    return best_anywhere

TESTS = [
    (([40, -25, 60, -90, 55, 30, -20, 15],), 85),
    (([-12, -3, -40],), -3),
    (([-7],), -7),
    (([5],), 5),
    (([3, -1, 4, -1, 5],), 10),
    (([0, 0, 0],), 0),
    (([10000] * 5,), 50000),
    (([2, -1, 2, -1, 2, -10, 4],), 4),
]

Pitfalls

• Starting best_anywhere at 0. On an all-negative log that returns 0, a run of no days, and [-12, -3, -40] gives 0 instead of -3. Seed both variables from the first day.
• Resetting best_here to 0 instead of to today's delta. The two are the same only when zero-length runs are allowed; here it hides every negative day and reports a run that does not exist.
• Updating best_anywhere before best_here. The answer then lags by one day and misses a peak that lands on the last entry.

Variants

• Crossing the pontoons — the same rolling state, but the recurrence looks two cells back and minimises.
• The rising traverse — drops the contiguity requirement, and that one change costs a linear scan per position.