Max Contiguous Subarray: Divide and Conquer

Question

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.

Answer 1

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])

Answer 2

After battling off-by-one errors, I managed to refactor after revisiting the computation model.

import math

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

        m = lo + (hi - lo) // 2
        L = solve_partition(lo, m)
        R = solve_partition(m, hi)

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

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

        return max(max(L, R), left_sum + right_sum)

    return solve_partition(0, len(A))

Output:

>>> print(max_subarray_sum([4, -1, 2, 1])
6

Recursion Tree, (maximum sum in brackets):

                [4, -1, 2, 1] (6)
                /            \
           [4, -1](3)         [2, 1](3) 
           /     \             /     \
        [4](4)   [-1](-1)     [2](2)  [1](1)
        /          \          /        \
       4           -1        2          1

Moving from mid to low appears to be just how the algorithm works, moving in the opposite direction, yields inaccurate results when calculating the cross section.