51. Minimum Value to Get Positive Step by Step Sum

Given an array nums, find the minimum positive value startValue such that the step-by-step cumulative sum (starting from startValue) is always >= 1 at every step.

startValue must be a positive integer.

Input: An integer array nums of length n.

Output: Integer — minimum positive startValue.

Examples

Input: [-3,2,-3,4,2]
Output: 5
Explanation: startValue=5: 5-3=2≥1, 2+2=4≥1, 4-3=1≥1, 1+4=5≥1, 5+2=7≥1. All ≥1. startValue=4 fails.

Input: [-1,2]
Output: 2
Explanation: startValue=2: 2-1=1≥1, 1+2=3≥1. Works. startValue=1 fails (1-1=0).

Input: [-2,-3,4]
Output: 6
Explanation: Prefix sums (from 0): -2,-5,-1. Min=-5. Need startValue+(-5)>=1 → startValue>=6.

Constraints

• 1<=nums.length<=100
• -100<=nums[i]<=100

Asked by