A small shop tracks one day's cash drawer activity as a sequence of n signed transactions, applied to the drawer in the given order: a positive value is a cash deposit and a negative value is a cash withdrawal. Before the first transaction of the day, the owner places some positive starting amount in the drawer. The owner needs the running drawer balance to stay at least 1 (never reach zero or go negative) after every single transaction in the sequence is applied. Find the smallest positive starting amount that guarantees this for the entire sequence of transactions.
Line 1: a single integer n, the number of transactions.
Line 2: n space-separated integers, the transactions in the order they are applied.
A single integer: the smallest positive starting balance such that the running balance stays at least 1 after every transaction.
Example 1
Input
5 -3 2 -3 4 2
Expected
5
Explanation
Running cumulative totals of the transactions alone are -3, -1, -4, 0, 2, so the lowest point reached is -4 (after the third transaction). With a starting balance of x, the balance after that point is x-4, which must be at least 1, so x must be at least 5. Starting at 5 gives balances 2, 4, 1, 5, 7 — all at least 1 — so the answer is 5.
Example 2
Input
4 1 2 3 4
Expected
1
Explanation
All transactions are deposits, so the running cumulative totals (1, 3, 6, 10) never dip below their first value of 1. The lowest point is 1, which already satisfies the at-least-1 requirement with a starting balance of just 1 (giving balances 2, 4, 7, 11). Since the starting balance must be positive, 1 is already the smallest possible choice, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →