3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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])
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.