Algorithm 1 – O(n^2): enumerate all possible subarray
This is pretty straightforward, but second program improves the performance by not repeating calculating sum.

def max_subarray_enum(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum(l))
    32
    """
    length = len(l)
    def sum(i, len):
        # assertion
        val = 0
        for n in range(0, len):
            val += l[i + n]
        return val
    # loop invariant:
    # l[i:i+len] is subarray which we need to calculate the sum
    # termination: enumerated all possible i j combinations
    max_val = l[0]
    for i in range(0, length):
        for subarray_len in range(1, length - i + 1):
            val = sum(i, subarray_len)
            if val > max_val: max_val = val
    return max_val

def max_subarray_enum2(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum2(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum2(l))
    32
    """
    length = len(l)
    # loop invariant:
    # l[i:i+len] is subarray which we need to calculate the sum
    # termination: enumerated all possible i j combinations
    max_val = l[0]
    for i in range(0, length):
        val = 0
        for subarray_len in range(1, length - i + 1):
            val += l[i + subarray_len - 1]
            if val > max_val: max_val = val
    return max_val

Algorithm 2 – O(nlogn): divide and conquer

def max_subarray_divide(l, left, right):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_divide(l, 0, len(l) - 1))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_divide(l, 0, len(l) - 1))
    32
    """
    # divide and conquer:
    # max = max_val(
    #   recur(firsthalf),
    #   recur(secondhalf),
    #   max_sum_left + max_sum_right
    # )
    def max_val(vals):
        # TODO: assert
        max = vals[0]
        for val in vals:
            if max < val: max = val
        return max
    def max_sum(start, end, step):
        if step > 0 and start > end:
            return 0
        elif step < 0 and end > start:
            return 0
        index_range = range(start, end + step, step)
        max = l[index_range[0]]
        sum = max
        for i in index_range[1:]:
            sum += l[i]
            if max < sum: max = sum
        return max

    if left > right:
        return 0  # actually, this one should be minus infinity
    if left == right:
        return l[left]

    mid = left + ((right - left) >> 1)
    # NOTE for the following statement, if we put max_sum(mid, right, 1)
    # then there will be dead recursive loop
    max_sum_right = max_sum(mid + 1, right, 1)
    max_sum_left = max_sum(mid, left, -1)
    max_sum_first = max_subarray_divide(l, left, mid)
    max_sum_right = max_subarray_divide(l, mid + 1, right)

    return max_val([max_sum_first, max_sum_right, max_sum_left + max_sum_right])

Algorithm 3 – O(n) with O(n) space: dynamic programming

def max_subarray(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray(l))
    32
    """
    # following are the dynamic programming vars:
    # - tail_max[n] means max subarray that ends at position n
    # - max[n] means max subarray in array l[0:n+1]
    #
    # following are the dynamic programming equations:
    # - tail_max[n] = max(tail_max[n-1]+l[n], l[n])
    # - max[n] = max(max[n-1], tail_max[n])
    #
    def max_val(a, b):
        return a if a > b else b
    # init data structures
    length = len(l)
    max = [None] * length
    tail_max = [None] * length
    # initial values
    if len(l) == 0:
        return 0
    max[0] = l[0]
    tail_max[0] = l[0]
    # dynamic programming: loop
    for n in range(1, length):
        tail_max[n] = max_val(tail_max[n-1]+l[n], l[n])
        max[n] = max_val(max[n-1], tail_max[n])
    return max[n]

Algorithm 4 – O(n) with O(1) space: dynamic programming with improvement

def max_subarray_o1space(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_o1space(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_o1space(l))
    32
    """
    def max_val(a, b):
        return a if a > b else b
    # initial values
    if len(l) == 0:
        return 0
    max_prev = l[0]
    tail_max_prev = l[0]
    # init data structures
    max = max_prev
    tail_max = tail_max_prev
    # dynamic programming: loop
    for n in range(1, len(l)):
        tail_max = max_val(tail_max_prev+l[n], l[n])
        max = max_val(max_prev, tail_max)
        tail_max_prev = tail_max
        max_prev = max
    return max

2D array?…
OK, I’ll ignore the code here….but it can be converted to 1D array like:

for upper_bound in range(0, first_dim_length(matrix)):
  for lower_bound in range(upper_bound, first_dim_length(matrix):
    merge the 2D array in within upper and lower bound to 1D array
    use dynamic programming approach to solve it