Maximize minus signs with positive prefix sums

You are given a list of positive integers nums = [a1, a2, ..., an]. Put a sign, + or -, in front of each number. Keep the order.

After each position i, the running total of the signed numbers (±a1 ± a2 ... ± ai) must be strictly greater than zero.

Return the largest number of - signs you can use while every running total stays positive.

def max_negative_signs(nums: list[int]) -> int: ...

Constraints

• 0 <= n <= 10^5
• 1 <= nums[i] <= 10^9

Example 1

nums = [4, 3, 1, 2]
output: 2

4 + 3 - 1 - 2 gives running totals 4, 7, 6, 4. Using 4 - 3 early leaves a total of 1, which then blocks both later values, so it is worse.

Example 2

nums = [1, 1, 1, 1]
output: 1

1 + 1 - 1 + 1 gives 1, 2, 1, 2. Any second - makes some running total 0, which is not allowed.

Note: the first number always gets +.