Longest run of customers a bank can serve

A bank opens with initial dollars in its vault (initial >= 0). Customers wait in a fixed queue, given as an integer array transactions: a positive value is a deposit and a negative value is a withdrawal of that size.

The bank may turn away any number of customers at the front of the queue and pick one customer to start with. From then on it must serve customers strictly in queue order. It stops as soon as the next customer's withdrawal would make the vault balance negative (a balance of exactly 0 is fine). That customer and everyone after them go unserved.

Implement:

def max_served(initial: int, transactions: list[int]) -> tuple[int, int, int]:
    ...

Return (count, start, end): the largest number of customers the bank can serve, and the half-open range [start, end) of the queue it serves. If several starts tie, return the earliest. If nobody can be served, return (0, 0, 0).

Constraints

• 0 <= len(transactions) <= 10^5
• -10^9 <= transactions[i] <= 10^9
• 0 <= initial <= 10^9

Example 1

initial = 1, transactions = [1, -3, 5, -2, 1]
result  = (3, 2, 5)

Starting at index 0 serves one customer (balance 2), then the withdrawal of 3 would leave -1. Starting at index 2 gives balances 6, 4, 5 and serves the last three customers.

Example 2

initial = 5, transactions = [4, -10, 3, 3, -5, -6]
result  = (4, 2, 6)

Starting at index 2 gives balances 8, 11, 6, 0. Ending at exactly 0 still counts.

Aim for better than O(n^2).

Reconstructed from the reported question; details may differ from what interviewers ask.