Maximum Sum Subarray - Return Subarray and sum - Divide and Conquer

Question

I need to return both the sum and the subarray for my maximum sum subarray algorithm that uses the divide and conquer approach.

I am able to compute the sum correctly in all of my tests. However, I am not able to compute the correct subarray.

class Results:
    max = 0
    maxSubArray = []
    start_index = 0
    stop_index = 0

def divide_and_conquer(arr, left, right):
    res = Results()

    maxLeftBorderSum = 0
    maxRightBorderSum = 0
    leftBorderSum = 0
    rightBorderSum = 0
    center = (left + right)//2

    if left == right:
        if(arr[left]>0):
            res.max = arr[left]
            res.start_index = left
            res.stop_index = right
            res.maxSubArray = arr[left:right]
            return res
        else:
            res.max = 0
            res.start_index = left
            res.stop_index = right
            res.maxSubArray = arr[:]
            return res

    maxLeft = divide_and_conquer(arr, left, center)
    maxRight = divide_and_conquer(arr, center+1, right)

    maxLeftSum = maxLeft.max
    maxRightSum = maxRight.max

    rightstopindex = 0
    leftstartindex = 0

    for i in range(center, left-1, -1):
        leftBorderSum = leftBorderSum + arr[i]
        if leftBorderSum > maxLeftBorderSum:
            maxLeftBorderSum = leftBorderSum
            leftstartindex = i

    for i in range(center+1, right+1):
        rightBorderSum = rightBorderSum + arr[i]
        if rightBorderSum > maxRightBorderSum:
            maxRightBorderSum = rightBorderSum
            rightstopindex = i

    res.max = max(maxLeftBorderSum + maxRightBorderSum, max(maxRightSum, maxLeftSum))

    if res.max == maxLeftBorderSum + maxRightBorderSum:
        res.start_index = leftstartindex
        res.stop_index = rightstopindex
        res.maxSubArray = arr[leftstartindex:rightstopindex]
    elif res.max == maxRightSum:
        res.start_index = maxRight.start_index
        res.stop_index = maxRight.stop_index
        res.maxSubArray = arr[maxRight.start_index:maxLeft.stop_index]
    else:
        res.start_index = maxLeft.start_index
        res.stop_index = maxLeft.stop_index
        res.maxSubArray = arr[maxLeft.start_index:maxLeft.stop_index]

    return res

Sample output

Array: 1 4 -9 8 1 3 3 1 -1 -4 -6 2 8 19 -10 -11

Correct subarray: 8 1 3 3 1 -1 -4 -6 2 8 19

My result: [8, 1, 3, 3, 1, -1, -4, -6, 2, 8]

my Sum (correct): 34

array: 2 9 8 6 5 -11 9 -11 7 5 -1 -8 -3 7 -2

correct subarray: 2 9 8 6 5

My result: [2, 9, 8, 6]

my Sum (correct):30

array: 10 -11 -1 -9 33 -45 23 24 -1 -7 -8 19

correct subarray: 23 24 -1 -7 -8 19

My subarray: [10, -11, -1, -9, 33, -45, 23, 24, -1, -7, -8]

my sum (correct): 50

array: 31 -41 59 26 -53 58 97 -93 -23 84

correct subarray: 59 26 -53 58 97

my subarray: [59, 26, -53, 58]

my sum (correct): 187

array: 3 2 1 1 -8 1 1 2 3

correct subarray3 2 1 1

my subarray[3, 2, 1, 1, -8, 1, 1, 2]

my sum (correct)7

array: 12 99 99 -99 -27 0 0 0 -3 10

correct subarray:12 99 99

my subarray[]

my sum (correct) 210

array: -2 1 -3 4 -1 2 1 -5 4

correct subarray 4 -1 2 1

my subarray [4, -1, 2]

my sum (correct) 6

There was a problem with the 2nd for loop. Should be rightstopindex = i + 1 — user3612719
– user3612719, Commented Jan 23, 2017 at 23:30
The issue appears when there are negative numbers in the array. — user3612719
– user3612719, Commented Jan 23, 2017 at 23:34

user3612719 · Accepted Answer · 2017-01-24 03:50:04Z

1

The following variables needed to be initialized differently. Because they were put as zero in the code above, sometimes they were never changed in the loops when the array only contained negative numbers.

maxLeftBorderSum = arr[center]
maxRightBorderSum = arr[center+1]
leftstartindex = center
rightstopindex = center+1

answered Jan 24, 2017 at 3:50

user3612719

1291 silver badge13 bronze badges

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

Collectives™ on Stack Overflow

Maximum Sum Subarray - Return Subarray and sum - Divide and Conquer

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