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


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)   [-1](-1)     (2)  (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.