Maximum sum sub array python

Question

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.

Yes, low and high are the index. As I mention in the question it is a Maximum sub array problem. — Rishabh Varshney
– Rishabh Varshney, Commented Jul 10, 2019 at 17:34

SchrgCat · Accepted Answer · 2019-07-11 00:31:25Z

2

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.

edited Jul 11, 2019 at 0:31

answered Jul 11, 2019 at 0:04

SchrgCat

5714 silver badges5 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Maximum sum sub array python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related