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.