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

Answer 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