Make the Prefix Sum Non-negative
Read values in order and keep a running sum; whenever it dips below zero, move the most negative value read so far to the end.
Read values in order and keep a running sum; whenever it dips below zero, move the most negative value read so far to the end.