An account starts at start and then sees a list of deposits (positive) and withdrawals (negative). Write balance_history(start: int, changes: list[int]) -> tuple[list[int], list[int]] that returns two lists, (balances, peaks), each of length len(changes) + 1:
balances[0] == start, andbalances[i]is the balance after the firstichanges;peaks[i]is the highest balance seen so far: the largest ofbalances[0]tobalances[i].
balance_history(100, [20, -50, 10, 40])
# ([100, 120, 70, 80, 120], [100, 120, 120, 120, 120])
balance_history(-5, [-3, 10])
# ([-5, -8, 2], [-5, -5, 2])
balance_history(7, [])
# ([7], [7])
0 <= len(changes) <= 2 * 10^5;startand each change are in[-10^9, 10^9].- Don't modify
changes.
⭐ Bonus: recomputing start + sum(changes[:i]) for every i is O(n²) and still passes; a speed test with 200,000 changes earns a star in O(n).
Show hint
itertools.accumulate(changes, initial=start) yields the running totals with start in front. Passing max as the function, accumulate(values, max), yields a running maximum.