Maximize Assigned Negative Signs

Question

You are given a sequence of n natural numbers a_1, a_2, ..., a_n, passed as the array arr. Put a sign, either "+" or "-", in front of every a_i so that each running total of the signed values, a_1 + a_2 + ... + a_i, stays strictly positive for every i with 1 <= i <= n. Under that requirement, make the number of "-" signs as large as possible and return that number. ...