Maximize the Array Sum After Negating at Most K Elements

Problem Overview

• Determine the maximum count of elements to negate in a positive-integer array so that every prefix sum remains strictly positive.
• Input: array A of positive numbers; Output: the maximum number of negations permitted under the prefix constraint.
• Real-world context: keep running totals (e.g., balances or resource levels) positive while applying sign changes.
• From Amazon interviews; a common coding interview problem and interview question.