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

[Exsul1]

I'm confused. The array as a whole is a subarray of the array, right? So the sum of all the positive numbers in the array is the maximum possible sum of all the possible subarrays, isn't it? Any other subarray made from removing a positive number or adding a negative number would have a smaller sum.

The keyword is "contiguous." The integers have to be next to each other in the array. You can't pick out only the positive integers.

Thus, the largest sum in the above example is the subarray [42, 14, -5, 86], which is 137. The sum of the entire array is smaller: 121.

---

Someone offered this, but I haven't been able to test or think through it yet:

def max_sum_contiguous(arr):
    running_totals = []
    running_total = 0
    for i, value in enumerate(arr):
        if value > -running_total:
            running_total += value
        else:
            running_total = 0
        running_totals.append(running_total)
    return max(running_totals)