Max Contiguous Subarray: Divide and Conquer I am conversant with Kadane's Algorithm. This is just an exercise in understanding divide and conquer as a technique.


  Find the maximum sum over all subarrays of a given array of positive/negative integers.


Here is what I have worked on but accumulating sum in solve_partition() looks pretty similar to solve_crossing_partition(), left and right sections. Am I duplicating computation?

I would also appreciate some guidance on the intuition behind moving from mid to low when calculating left_sum: for i in range(m, lo - 1, -1): ...

import math


def max_subarray_sum(A):
    def solve_crossing_partition(m, lo, hi):

        left_sum = -math.inf
        _sum = 0
        for i in range(m, lo - 1, -1):
            _sum += A[i]
            left_sum = max(left_sum, _sum)

        right_sum = -math.inf
        _sum = 0
        for j in range(m + 1, hi):
            _sum += A[j]
            right_sum = max(right_sum, _sum)

        return left_sum + right_sum

    def solve_partition(lo, hi):
        if lo == hi:
            return A[lo]

        max_sum = -math.inf
        _sum = 0

        for i in range(lo, hi):
            _sum += A[i]
            max_sum = max(max_sum, _sum)

        return max_sum

    if not A:
        return 0

    m = len(A) // 2
    L = solve_partition(0, m + 1)
    R = solve_partition(m + 1, len(A))
    X = solve_crossing_partition(m, 0, len(A))

    return max(max(L, R), X)

if __name__ == "__main__":
    for A in (
        [],
        [-2, 1, -3, 4, -1, 2, 1, -5, 4],
        [904, 40, 523, 12, -335, -385, -124, 481, -31],
    ):
        print(max_subarray_sum(A))


Output:

0
6
1479


I followed this ref.
Nested max
max(max(L, R), X)

can be
max((L, R, X))

Actual tests
Assert what you're expecting:
assert 0 == max_subarray_sum([])
assert 6 == max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
assert 1479 == max_subarray_sum([904, 40, 523, 12, -335, -385, -124, 481, -31])