Smallest Starting Balance
Easy · prefix sum
You are about to work through a list of money movements nums in order. Each number is added to your balance: a positive number is a deposit and a negative number is a withdrawal.
You choose the balance you start with, which must be a positive whole number. After every single movement your balance has to be at least 1, otherwise the plan fails.
Return the smallest starting balance that makes the plan work.
Examples
Example 1
Input: nums = [-3, 2, -3, 4, 2]
Output: 5
Starting at 5 the balance goes 2, 4, 1, 5, 7 and never drops below 1. Starting at 4 it would reach 0 after the third movement.
Example 2
Input: nums = [1, 2]
Output: 1
The balance only grows, so the smallest allowed start of 1 is enough.
Example 3
Input: nums = [1, -2, -3]
Output: 5
Starting at 5 the balance goes 6, 4, 1.
Constraints
- 1 <= len(nums) <= 300
- -100 <= nums[i] <= 100