Longest run of customers a bank can serve

The bank picks one starting customer, then serves the queue in order until the
next customer would push the balance below zero. A choice of start therefore
serves a contiguous run transactions[l..r] such that every running balance
initial + sum(transactions[l..i]) for l <= i <= r stays non-negative. We
want the longest such run.

Brute force, O(n^2). For every start l, walk right and keep a running
balance; stop at the first negative balance and record the length. This is the
right thing to say first, and it is the oracle for testing.

Optimal: one sliding window, O(n). Move right across the array and keep a
window [left, right] together with balance = initial + sum(window).

1. Add transactions[right] to balance.
2. While balance < 0, drop transactions[left] and advance left.
3. The window is now valid; update the best length.

Why the window stays valid after shrinking, not only its total. Before
right was added, every prefix of [left, right-1] was non-negative (the
invariant). Suppose, after shrinking to left', the total of [left', right]
is >= 0 but some inner prefix [left', i] with i < right is negative.
Call A = sum(left'..i) and B = sum(i+1..right), so initial + A < 0 and
initial + A + B >= 0, which forces B > 0. But the old window satisfied
initial + S + A >= 0 (with S the removed part) and initial + S + A + B < 0,
which forces B < 0. Contradiction, so every prefix of the new window is
non-negative.

Why it is optimal. left only moves when the window ending at right is
invalid. Any start l < left was dropped because some window [l, r'] with
r' <= right went negative, so l cannot serve through right either. So for
each right the window holds the earliest valid start, and the maximum over
all right is the answer.

Invariant: after step 2, balance == initial + sum(transactions[left:right+1])
and every prefix of that slice keeps the balance >= 0.

from typing import List, Tuple


def max_served(initial: int, transactions: List[int]) -> Tuple[int, int, int]:
    """Return (count, start, end) for the longest run of customers the bank
    can serve back to back. `end` is exclusive. If nobody can be served,
    return (0, 0, 0).

    A run [l, r) is servable when initial + sum(transactions[l..i]) >= 0
    for every i in [l, r).
    """
    best = (0, 0, 0)
    balance = initial
    left = 0
    for right, amount in enumerate(transactions):
        balance += amount
        # Shrink from the left until the window ending at `right` is valid.
        # After this loop every prefix of transactions[left:right+1]
        # keeps the balance non-negative.
        while balance < 0 and left <= right:
            balance -= transactions[left]
            left += 1
        count = right - left + 1
        if count > best[0]:
            best = (count, left, right + 1)
    return best


def brute_force(initial: int, transactions: List[int]) -> int:
    """O(n^2) oracle: try every start and serve until the balance breaks."""
    best = 0
    for l in range(len(transactions)):
        balance = initial
        for r in range(l, len(transactions)):
            balance += transactions[r]
            if balance < 0:
                break
            best = max(best, r - l + 1)
    return best


if __name__ == "__main__":
    assert max_served(1, [1, -3, 5, -2, 1]) == (3, 2, 5)
    assert max_served(5, [4, -10, 3, 3, -5, -6]) == (4, 2, 6)
    assert max_served(0, [-1, -2]) == (0, 0, 0)
    assert max_served(10, [-3, -3, -3, -3]) == (3, 0, 3)

    import random
    for _ in range(5000):
        arr = [random.randint(-6, 6) for _ in range(random.randint(0, 10))]
        k = random.randint(0, 6)
        assert max_served(k, arr)[0] == brute_force(k, arr)
    print("ok")

• max_served: O(n) time. Each index enters the window once and leaves at
  most once, so the inner loop runs at most n times in total. O(1) extra space.
• brute_force: O(n^2) time, O(1) space.

• initial = 1, transactions = [1, -3, 5, -2, 1] -> (3, 2, 5): start at the
  deposit of 5; balances 6, 4, 5.
• initial = 5, transactions = [4, -10, 3, 3, -5, -6] -> (4, 2, 6):
  balances 8, 11, 6, 0. A balance of exactly 0 is still allowed.
• initial = 0, transactions = [-1, -2] -> (0, 0, 0): nobody can be served.
• initial = 0, transactions = [] -> (0, 0, 0): empty queue.
• initial = 10, transactions = [-3, -3, -3, -3] -> (3, 0, 3): the fourth
  withdrawal would leave -2.
• initial = 0, transactions = [2, -2, 0, -1, 4] -> (3, 0, 3): ties keep the
  earliest start.
• All deposits, e.g. initial = 0, [1, 2, 3] -> (3, 0, 3).
• Large values: Python ints do not overflow; in Java or C++ use 64-bit balances.

1. Return every optimal start, or the earliest/latest one. Keep the
   comparison > for earliest, switch to >= for latest, or collect all
   left values that reach the best length.
2. Answer many queries with different initial amounts. Precompute prefix
   sums P. A start l with amount k serves up to the first i >= l with
   P[i+1] < P[l] - k. Build a sparse table of range minimums on P and
   binary search per start, O(n log n) per query, or sort queries by k and
   process offline. For a single fixed start, one binary search on the range
   minimum answers each query in O(log n).
3. The queue is circular (after the last customer comes the first again,
   each customer served at most once). Run the same window over the array
   concatenated with itself and cap the window length at n. Still O(n).
4. The bank may skip up to m customers inside the run (a skipped
   withdrawal costs nothing). For a fixed start, skip the m largest
   withdrawals seen so far: keep them in a min-heap of size m, and when a
   larger withdrawal arrives, swap it in and charge the smaller one instead.
   That is O(n log m) per start. Across all starts the window must also
   remove items from the heap, so use a sorted container, a good Staff-level
   discussion.
5. Transactions arrive as a stream. The window algorithm is already
   online: it needs only the current window, which you hold in a deque. Report
   the best run so far after each arrival.

Mid-level (L4)

• Restates the rule as "longest contiguous run where every running balance
  is non-negative" and asks whether a balance of 0 is allowed.
• Writes the O(n^2) brute force correctly, then reaches the sliding window
  with hints.
• Handles empty input and the case where nobody can be served.

Senior (L5)

• Goes straight to the O(n) window and explains why the shrunk window is
  valid at every prefix, not only in total.
• States the amortized argument for O(n) and tests with a brute-force oracle.
• Discusses overflow in fixed-width languages and how ties are broken.

Staff (L6+)

• Gives a clean optimality proof (the window holds the earliest valid start
  for each end).
• Handles multi-query and circular variants with prefix sums, range minimums
  and the doubled array, and names the trade-offs.
• Reasons about the skip-m variant and why a simple window no longer
  suffices, and proposes a heap-based approach with its complexity.