CODEWITHSUNDEEP
python-3.xalgorithmmaxdivide-and-conquersub-array
Rishabh Varshney
Rishabh Varshney

Reputation: 35

Maximum sum sub array python

I am following the book 'Introduction to Algorithm' and use the algorithm given for making the program but the program is not working as expected.

probably the sum of previous function is adding to the new sum and thus it is printed I don't know how. When I put a single element list the output is as expected but when I put 2 or more element list say [2,3] I get output 4 which is not expected

def max_crossing_subarray(array,low,mid,high):
    left_sum = -1000
    sum_ar = 0

    for i in range(mid, low-1, -1):
        sum_ar = sum_ar + array[i]
        if sum_ar>left_sum:
            left_sum = sum_ar
            max_left = i

    right_sum = -1000
    sum_ar = 0

    for i in range(mid,high):
        sum_ar = sum_ar + array[i]
        if sum_ar>right_sum:
            right_sum = sum_ar
            max_right = i

    return [max_left, max_right, left_sum + right_sum]

def max_subarray(array, low, high):
    if low==high:
        return [low, high, array[low]]
    else:
        mid = int((low + high)/2)
        left_low, left_high, left_sum = max_subarray(array, low, mid)
        right_low, right_high, right_sum = max_subarray(array,mid+1,high)
        cross_low, cross_high, cross_sum = max_crossing_subarray(array, 
low, mid, high)

        if left_sum>=right_sum and left_sum>=cross_sum:
            return [left_low, left_high, left_sum]
        elif right_sum>=left_sum and right_sum>=cross_sum:
            return [right_low, right_high, right_sum]
        else:
            return [cross_low, cross_high, cross_sum]

arr = [2,3]
ar= max_subarray(arr, 0, len(arr)-1)
print(ar)

When I input the list [2] I got the output [0, 0, 2] #[low, high, sum] but for [2,3] and [2,5] I got output as [0, 0, 4] and [1, 1, 5] respectively which is not as expected.

Upvotes: 0

Views: 169

Answers (1)

SchrgCat
SchrgCat

Reputation: 561

While calculating max crossing subarray, in second for statement range should start at mid + 1 and end at high + 1. Firstly mid element right now is added to both left and right sum, secondly you finish summing at element before the last one.

Upvotes: 2

Related Questions