Skills101
← All coding problems

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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.