Implements maximum subarray algorithm as described in: https://en.wikipedia.org/wiki/Maximum_subarray_problem

max_subarray.py

def max_subarray(xs):
    if not xs:
        return [], 0
    start = 0
    end = 1
    cur_sum = 0
    max_sum = xs[0]
    for i in range(len(xs)):
        tmp_sum = cur_sum + xs[i]
        if xs[i] > tmp_sum:
            cur_sum = xs[i]
            start = i
        else:
            cur_sum = tmp_sum
        if cur_sum > max_sum:
            max_sum = cur_sum
            end = i + 1
    return xs[start:end], max_sum
  

Python repl:

>>> print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
([4, -1, 2, 1], 6)

>>> print(max_subarray([]))
([], 0)