745. The Smallest Safe Starting Value
A counter starts at some positive value s and the ith step adds a[i], which may be
negative. Print the SMALLEST s that is at least 1 and keeps the counter at or above 1 after
every single step.
-3 2 -3 4 2 -> 5
1 2 -> 1
1 -2 -3 -> 5
-1 -> 2
## The lowest point decides everything
Starting from s, the counter after i steps is s plus the ith prefix sum. So every step
stays at or above 1 exactly when
s + (the smallest prefix sum) >= 1
Only the MINIMUM prefix matters; every other step is comfortably above it by construction. Rearranged:
s = 1 - (the smallest prefix sum)
Reducing a condition that must hold at every step to a condition on a single extreme is the
idea here, and it is what turns a search over s into one pass.
## Two things that both pin the answer
`s` must be at least 1 on its own, by the statement. If every prefix sum is positive the formula gives something less than 1, so the answer is
max(1, 1 - minimum prefix)
On 1 2 the minimum prefix is 1, the formula gives 0, and the answer is 1. That case is in the
samples.
## The minimum must include the empty prefix
The minimum is taken over every prefix sum after at least one step, AND over the empty prefix,
whose sum is 0. The empty prefix belongs in there because a counter that only ever rises still
needs s >= 1, and keeping 0 in the minimum is what expresses that.
Initialising the running minimum to 0 before the loop covers both at once, which is why the
code reads mn = 0 rather than mn = a[0]. It also makes the minimum at most 0, so
1 - mn is never below 1 and the max(1, ...) above becomes a second guard on the same
case rather than the only one.
## The off-by-one in the 1
The requirement is at or above 1, not above 0. Writing s = -min allows the counter to touch
0, and every test with a prefix minimum of exactly -s catches it. On -1 the minimum prefix
is -1, so s must be 2, not 1.
## Relationship with problem 744
744 takes the running MAXIMUM of the same prefix sums. This takes the running minimum. One sweep, two extremes, two different questions.
## Overflow
10^5 steps of 10^4 reach 10^9 in either direction.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 100000` - `-10^4 ≤ each value ≤ 10^4`
Input
The first line contains an integer n.
The second line contains n integers, which may be negative.
Output
Print one integer, the smallest safe starting value.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.