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)

Have you tried a pen and paper example and debugged if your code does the same as you on your paper? — MrSmith42
I am using a book, and the book has this algorithm listed. Plus I have searched and found the same algorithm elsewhere. What I don't understand is the recursive part. And I think that is where, the problem is coming from. I need some further explanation. Where I am confused... I have already learnt recursion and got its examples to work. But can't figure out how it is being used here. — Clinton Yeboah
If you have a better soultion, please elaborate it. I want to understand it. I previously tried merge sort, but couldn't get it to work at all. — Clinton Yeboah
Kadane's algorithm is appropriate for this... Why do you want to complicate things using divide and conquer? — User_Targaryen
Thanks @User_Targaryen I have seen that algorthm. As I said, is not about getting it to work. I want to understand the divide and conquer algorithm. I tried merge sort with divide and conquer, I failed and this one too. It's in my syllabus. I have to understand it — Clinton Yeboah

tim_yates tim_yates · Accepted Answer · 2016-09-05T13:14:44

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]

Maximum SubArray Using Divide and Conquer

1 Answers