find-subarray.py

def exhaustive(v):
    n = len(v)

    best = [None, None]
    max_sum = 1e-9
    for i in range(n):
        for j in range(i + 1, n):
            if sum(v[i:j + 1]) > max_sum:
                max_sum = sum(v[i:j + 1])
                best = [i, j + 1]

    return v[best[0]:best[1]]


def find_max(v):
    n = len(v)
    integ = [sum(v[:i+1]) for i in range(n)]

    # zero-pad so we can always do f[i] - f[j]
    integ = [0] + integ

    best = [None, None]
    max_sum = -1e9
    for i in range(n):
        left = integ[i + 1:]
        j = left.index(max(left)) + i
        if integ[j] - integ[i] > max_sum:
            max_sum = integ[j] - integ[i]
            best = [i, j + 1]

    return v[best[0]:best[1]]


if __name__ == '__main__':
    v = [-1, 2, 4, -8, 2, 2, 4, -3, 2, 1]
    o1, o2 = find_max(v), exhaustive(v)
    assert(all([True if a == b else False for a, b in zip(o1, o2)]))
    print(v)
    print(o1, sum(o1))

    print()
    v = [1, 2, 3, 4, 5, 6]
    o1, o2 = find_max(v), exhaustive(v)
    assert(all([True if a == b else False for a, b in zip(o1, o2)]))
    print(v)
    print(o1, sum(o1))

    import numpy as np
    print()
    v = [x for x in np.random.randint(-5, 10, 10)]
    o1, o2 = find_max(v), exhaustive(v)
    assert(all([True if a == b else False for a, b in zip(o1, o2)]))
    print(v)
    print(o1, sum(o1))