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

[Exsul1]

It works. I tested the function that runs in linear time against my quadratic-time solution 10,000 times, and both give the same result, no matter what integers are in the array:

import random

# Given an array of integers, find the maximum sum
# of all possible contiguous subarrays of the array

def max_subarray_sum_quadratic(arr):
    max_sum = 0
    for mindex in range(0, len(arr)):
        for maxdex in range(mindex + 1, len(arr) + 1):
            subarray_sum = 0
            for each_int in arr[mindex:maxdex]:
                subarray_sum += each_int
            if subarray_sum > max_sum:
                max_sum = subarray_sum
    return max_sum

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


for r in range(10000):
    whole_array = []
    for r2 in range(6):
        whole_array.append(random.randint(-100, 100))
    if max_subarray_sum_quadratic(whole_array) != max_subarray_sum_linear(whole_array):
        print("\nArray:", whole_array)
        print(max_subarray_sum_quadratic(whole_array), "quadratic")
        print(max_subarray_sum_linear(whole_array), "linear")

Now I just have to figure out how the linear-time function is working exactly. I'm slow at math.