In linear time, find the maximum sum of all possible contiguous subarrays

[DPaul]

Hi,

I gave this "interview question" some considerable thought, because I want to get hired next time.
My basic idea was to reduce the size of the original array, effectively reducing the number of possible subarrays.
There are about 10 rules you can formulate: e.g. a candidate subarray cannot start with a negative number or zero etc..
(You need to make proviso's for all negative arrays, which happen frequently if you do (-100, 10, k=30)
This is a dummy example:

Output:
arr = [-1,-2, 3, 4, 5,-6, 7, 8, 0,-9,-10, 11,-12]
newarr = [ 12,-6, 15,-19, 11]

Unfortunately, every "if" comes with a penalty of about 0.1 secs in 100_000 runs. It is a trade-off, and I was not
able to write a "reducing" algorithm, that was fast enough to my taste. (Another interview question?)
So I ended up with a solution along the lines what was proposed above, yielding about 1.5 secs for 100_000 runs.
Paul

maxArr = [max(arr)]
subarr = 0
for number in arr:
    subarr += number
    if subarr > 0:
        maxArr.append(subarr)
    else:
        subarr = 0
maxarr = max(maxArr)