Maximum SubArray Using Divide and Conquer

Question

I am learning Algorithms from a book 'An Introduction To Algorthms'. I want to implement a divide and conquer algorithm to find the maximum sub-array of an array. Here is my solution, but I am getting the wrong results.

Any help will be appreciated. Please explain, as I am more interested in understanding it more than getting it to work. Thank you.

def maxNumber(int a, int b){
return a > b ? a : b;
}

def maxNumber(List a, List b, List c){
return maxNumber(a.sum(), maxNumber(b.sum(), c.sum()))
}

//int sum(List list){
//    int sum = 0
//    list.each {
//        sum+= it
//    }
//    sum
//}

def maxCrossing(ArrayList<Integer> list, int low, int mid, int high){
int sum = 0
int leftSum = Integer.MIN_VALUE
int maxLeftIndex = -1

/*for (int i = low; i <= mid ; i++) {
    sum += list[i]
    if (sum > leftSum) {
        leftSum = sum
        maxLeftIndex = i
    }

}*/

for (int i = mid; i >= low ; i--) {
    sum += list[i]
    if (sum > leftSum) {
        leftSum = sum
        maxLeftIndex = i
    }

}

sum = 0
int rightSum = Integer.MIN_VALUE
int maxRightIndex = -1

for (int i = mid + 1; i <= high ; i++) {
    sum += list[i]
    if (sum > rightSum) {
        rightSum = sum
        maxRightIndex = i
    }

}

def returnList  = []
for (int i = maxLeftIndex; i < maxRightIndex + 1; i++) {
    returnList.add(list[i])
}
return returnList
}

def maxSubArray(ArrayList<Integer> list,int low, int high){
if (low == high) return [list[low]]

int mid = (low + high) / 2

def leftResults = maxSubArray(list, low, mid)
def rightResults = maxSubArray(list, mid + 1, high)
def crossResults = maxCrossing(list, low, mid, high)

/*if (rightResults[2] > leftResults[2] && rightResults[2] > crossResults[2]) return rightResults
if (leftResults[2] > rightResults[2] && leftResults[2] > crossResults[2]) return leftResults
else return crossResults*/


maxNumber(leftResults, rightResults, crossResults)
}

//Testing Features 
println("Enter array members")
ArrayList<Integer> myList =  [-2, -5, 10, -2, -3, 1, 5, -6]  //System.in.newReader().readLines()
int size = myList.size()
def maxSum = maxSubArray(myList, 0, size - 1)
println("Maximum sub-array is: " + maxSum)

Answer 1

Think one of your main issues was a lack of braces round the if statements in maxCrossing

So:

if (sum > leftSum) leftSum = sum
maxLeftIndex = i

should be:

if (sum > leftSum) {
    leftSum = sum
    maxLeftIndex = i
}

Also, I believe when checking the lower part of the crossing, you need to start from the mid point and work down (may be wrong here)

Also, passing back indexes and a sum doesn't make much sense... I changed it to just return the max array from each step (which we can then call sum() on)

Here's a (I think) working solution from your code:

def maxResults(List a, List b, List c) {
    a.sum() > b.sum() && a.sum() > c.sum() ? a :
    b.sum() > c.sum() ? b :
    c
}

def maxCrossing(List list, int low, int mid, int high){
    int sum = 0
    int leftSum = Integer.MIN_VALUE
    int maxLeftIndex = -1

    for (int i = mid; i >= low; i--) {
        sum += list[i]
        if (sum > leftSum) {
            leftSum = sum
            maxLeftIndex = i
        }
    }

    sum = 0
    int rightSum = Integer.MIN_VALUE
    int maxRightIndex = -1

    for (int i = mid + 1; i <= high ; i++) {
        sum += list[i]
        if (sum > rightSum) {
            rightSum = sum
            maxRightIndex = i
        }
    }

    return list[maxLeftIndex..maxRightIndex]
}

def maxSubArray(List list, int low, int high){
    if (low == high) return [list[low]]

    int mid = (low + high) / 2

    def leftResults = maxSubArray(list, low, mid)
    def rightResults = maxSubArray(list, mid + 1, high)
    def crossResults = maxCrossing(list, low, mid, high)

    maxResults(rightResults, leftResults, crossResults)
}

//Testing Features
println("Enter array members")
ArrayList<Integer> myList =  [-2, -5, 10, -2, -3, 1, 5, -6]   //System.in.newReader().readLines()
int size = myList.size()
def maxSum = maxSubArray(myList, 0, size - 1)
println("Maximum sub-array is: " + maxSum)

Btw, the output from this is:

Maximum sub-array is: [10, -2, -3, 1, 5]