Maximize Negative Signs

Problem Overview

• Given n natural numbers, assign + or − to each so every prefix sum stays strictly positive while maximizing how many negatives are used.
• Input: one line with n numbers a1..an; Output: one integer, the maximum count of negative signs under the constraint.
• Constraints: 1 ≤ n ≤ 100000, 1 ≤ ai ≤ 1e9.
• Real-world context: sequence planning of gains/losses to keep a running balance positive.
• Asked in Amazon interviews; a coding interview problem and interview question.