One of my ideas was watching the value of sum and if it reached a negative value then break out of the inner loop.

Until you get something like this.....

my @array = qw( -25 -3 -10 -30 -1 -2 -1 -4 -23 );
[download]

(I used to write test cases for my colleges CS club's High School programming contest).