Minimum Starting Energy
easyArrays & Prefix Sums+10 XPTime limit 2s
A player walks through n rooms in order. Room i changes her energy by a[i] (a potion is positive, a trap is negative). She starts with some positive energy E, and her energy must stay at least 1 after every room. Find the smallest starting energy E that makes this possible.
Input:
- line 1:
n - line 2:
nintegers
Output: the minimum starting energy (always at least 1).
Constraints: 1 ≤ n ≤ 10⁵, −10⁴ ≤ a[i] ≤ 10⁴.
Think about it: energy after room i is E + prefix[i]. The worst moment is the lowest prefix sum, so E must satisfy E + minPrefix ≥ 1.
Sample input 1
5 -3 2 -3 4 2
Sample output 1
5
Sample input 2
3 1 2 3
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).