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

[deanhystad]

import random

def mymax(array):
    '''Find sub-array of array with the largest sum.
    Return (sum, start_index, end_index)
    '''
    subsum = start = 0
    maxsum = [subsum, start, start]
    for index, value in enumerate(array):
        subsum += value
        if subsum > maxsum[0]:
            # Found a new maximum
            maxsum = [subsum, start, index]
        elif subsum <= 0:
            # No future maxsums will contain anything from array[:index].  Look for max sub_array sum for array[i+1:]
            subsum = 0
            start = index + 1
    return maxsum

def gribmax(array):
    '''Solution from Griboullis for finding greatest sum of consecutive array values'''
    mv = sv = best = 0
    for value in array:
        sv += value
        mv = min(mv, sv)
        best = max(best, sv-mv)
    return best

x = random.choices(range(-100, 100), k=30)
print(x)
print(mymax(x))
print(gribmax(x))

My solution and Griboullis' solution agree when run on 100,000 different random arrays of length 100.