0

I want to implement Maximum Sub Array problem with an algorithm that exhibits (n log n):

Find the maximum contigous sub array, or maximum sum of contiguous elements in the array.

Assumption:not all elements are negative numbers

I have somewhat working solution; the problem is with the overlapping center array, and the appropriate indexes that designate overlapping sub problems, some arrays Im getting the right answer on other not.

Just for comparison & for cheking correctness I implemented a solution known as Kadane’s algorithm (I believe the complexity is Omega(n)).

This is Kandane’s algorithm(http://en.wikipedia.org/wiki/Maximum_subarray_problem):

 public static void Kadane(int array[]) {
        int max_ending_here = 0;
        for (int i = 0; i < array.length; i++) {
            max_ending_here = max_ending_here + array[i];
            max_so_far = Math.max(max_so_far, max_ending_here);
        }
        System.out.println("Kadane(int array []): " + max_so_far);
    }

My recursive implementation, that uses divide & conquer to compare sub array's max's , then make's recursive call on the sub array that has the max, until the recursion ends

public static void findMaxSubArray(int[] array, int lowIndex, int highIndex) {

        int mid = 0;
        int arrayLength = 0;
        int maxEndingHere = 0;

        if (array == null) {
            throw new NullPointerException();
        } else if 
                //base condition 
           (array.length < 2 || (highIndex==lowIndex)) {
            maxLowIndex = lowIndex;
            maxHighIndex = highIndex;
            System.out.println("findMaxSubArray(int[] array, int lowIndex, int highIndex)");
            System.out.println("global Max Range, low:" + maxLowIndex + " high: " + maxHighIndex);
            System.out.println("global Max Sum:" + globalMaximum);
        } else {
            System.out.println();
            int lowMidMax = 0;
            int midHighMax = 0;
            int centerMax = 0;
            //array length is always the highest index +1 
            arrayLength = highIndex + 1;

            //if even number of elements in array 
            if (array.length % 2 == 0) {
                mid = arrayLength / 2;
                System.out.println("low: " + lowIndex + " mid: " + mid);
                for (int i = lowIndex; i < mid; i++) {
                    System.out.print(array[i] + ",");
                }
                //calculate maximum contigous array encountered so far in low to mid indexes 
                for (int i = lowIndex; i < mid; i++) {
                    maxEndingHere = maxEndingHere + array[i];
                    if (maxEndingHere < 0) {
                        maxEndingHere = 0;
                    }

                    if (globalMaximum < maxEndingHere) {
                        //new maximum found 
                        globalMaximum = lowMidMax = maxEndingHere;
                        lowIndex = i;
                    }

                }
                //end low mid calc 

                for (int i = mid; i <= highIndex; i++) {
                    System.out.print(array[i] + ",");
                }
                System.out.println("mid: " + mid + " high: " + highIndex);
                //calculate maximum contigous array encountered so far in mid to high indexes 
                for (int i = mid; i <= highIndex; i++) {
                    maxEndingHere = maxEndingHere + array[i];
                    if (maxEndingHere < 0) {
                        maxEndingHere = 0;
                    }

                    if (globalMaximum < maxEndingHere) {
                        //new maximum found 
                        globalMaximum = midHighMax = maxEndingHere;
                        mid = i;
                    }

                }
//end mid high calc
                //calculate maximum contigous array encountered so far in center array
                int lowCenter = mid -1;
                int highCenter = highIndex -1;

                System.out.println("lowCenter: " + lowCenter + " highCenter: " + highCenter);
                for (int i = lowCenter; i < highCenter; i++) {
                    System.out.print(array[i] + ",");
                }
                //calculate maximum contigous array encountered so far in low to mid indexes 
                for (int i = lowCenter; i < highCenter; i++) {
                    maxEndingHere = maxEndingHere + array[i];
                    if (maxEndingHere < 0) {
                        maxEndingHere = 0;
                    }

                    if (globalMaximum < maxEndingHere) {
                        //new max found
                        globalMaximum = centerMax = maxEndingHere;
                        lowCenter = i;

                    }

                }
                //end center calc 
                //determine which range contains the maximum sub array 
                //if lowMidMax <= midHighMax and centerMax
                if (lowMidMax >= midHighMax && lowMidMax >= centerMax) {
                    maxLowIndex = lowIndex;
                    maxHighIndex = mid;
                    //recursive call
                    findMaxSubArray(array, lowIndex, mid);
                }
                if (midHighMax >= lowMidMax && midHighMax >= centerMax) {
                    maxLowIndex = mid;
                    maxHighIndex = highIndex;
                    //recursive call
                    findMaxSubArray(array, mid, highIndex);
                }
                if (centerMax >= midHighMax && centerMax >= lowMidMax) {
                    maxLowIndex = lowCenter;
                    maxHighIndex = highCenter;
                    //recursive call
                    findMaxSubArray(array, lowCenter, highCenter);
                }

            }//end if even parent array 
            //else if uneven array 
            else {
                mid = (int) Math.floor(arrayLength / 2);
                System.out.println("low: " + lowIndex + " mid: " + mid);
                for (int i = lowIndex; i < mid; i++) {
                    System.out.print(array[i] + ",");
                }
                //calculate maximum contigous array encountered so far in low to mid indexes 
                for (int i = lowIndex; i < mid; i++) {
                    maxEndingHere = maxEndingHere + array[i];
                    if (maxEndingHere < 0) {
                        maxEndingHere = 0;
                    }

                    if (globalMaximum < maxEndingHere) {
                        //new maximum found 
                        globalMaximum = lowMidMax = maxEndingHere;
                        lowIndex = i;
                    }

                }
                //end low mid calc
                System.out.println("mid+1: " + (mid + 1) + " high: " + highIndex);
                for (int i = mid + 1; i <= highIndex; i++) {
                    System.out.print(array[i] + ",");
                }
                //calculate maximum contigous array encountered so far in mid to high indexes 
                for (int i = mid + 1; i <= highIndex; i++) {
                    maxEndingHere = maxEndingHere + array[i];
                    if (maxEndingHere < 0) {
                        maxEndingHere = 0;
                    }

                    if (globalMaximum < maxEndingHere) {
                        //new maximum found 
                        globalMaximum = midHighMax = maxEndingHere;
                        mid = i;
                    }

                }
                //end mid high calc
                //calculate maximum contigous array encountered so far in center array
                int lowCenter =  mid;
                int highCenter = highIndex -1;

                System.out.println("lowCenter: " + lowCenter + " highCenter: " + highCenter);
                for (int i = lowCenter; i < highCenter; i++) {
                    System.out.print(array[i] + ",");
                }
                //calculate maximum contigous array encountered so far in low to mid indexes 
                for (int i = lowCenter; i < highCenter; i++) {
                    maxEndingHere = maxEndingHere + array[i];
                    if (maxEndingHere < 0) {
                        maxEndingHere = 0;
                    }

                    if (globalMaximum < maxEndingHere) {
                        //new max
                        globalMaximum = centerMax = maxEndingHere;
                        lowCenter = i;
                    }

                }
                //end center calc 

                //determine which range contains the maximum sub array 
                //if lowMidMax <= midHighMax and centerMax
                  if (lowMidMax >= midHighMax && lowMidMax >= centerMax) {
                    maxLowIndex = lowIndex;
                    maxHighIndex = mid;
                    //recursive call
                    findMaxSubArray(array, lowIndex, mid);
                }
                if (midHighMax >= lowMidMax && midHighMax >= centerMax) {
                    maxLowIndex = mid;
                    maxHighIndex = highIndex;
                    //recursive call
                    findMaxSubArray(array, mid, highIndex);
                }
                if (centerMax >= midHighMax && centerMax >= lowMidMax) {
                    maxLowIndex = lowCenter;
                    maxHighIndex = highCenter;
                    //recursive call
                    findMaxSubArray(array, lowCenter, highCenter);
                }


            }//end odd parent array length 
        }//end outer else array is ok to computed 

    }//end method

Results : using array subArrayProblem1 = {1, 2, 3, 4, 5, 6, 7, 8};

Kadane(int array []): 36 low: 0 mid: 4 1,2,3,4,5,6,7,8,mid: 4 high: 7 lowCenter: 6 highCenter: 6

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:7 high: 7 global Max Sum:36 BUILD SUCCESSFUL (total time: 0 seconds)

Issues although the global max sum is correct when compared to Kadane, the low index & high index range reflects the last recusive call.

Results : using array subArrayProblem = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};

Kadane(int array []): 1607 low: 0 mid: 8 100,113,110,85,105,102,86,63,mid+1: 9 high: 16 101,94,106,101,79,94,90,97,lowCenter: 16 highCenter: 15

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:16 high: 16 global Max Sum:1526

The global max is not correct, note the difference is actually 1 element , which is the element 81

Improve this question

2 Answers 2

Reset to default
2

A cleaner way to find subarray with the maximum sum (D/C recursive way) :

// A Divide and Conquer based Java solution
// To find a subarray with the maximum sum

import java.util.Arrays;
import java.util.Scanner;

class MaxSubArray {

    private static Result maxCrossingSum(int arr[], int l, int m, int h) {

        int sum = 0;
        int maxLeft = 0;
        int leftSum = Integer.MIN_VALUE;
        for (int i = m; i >= l; i--) {
            sum = sum + arr[i];
            if (sum > leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }

        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        int maxRight = arr.length - 1;
        for (int i = m + 1; i <= h; i++) {
            sum = sum + arr[i];
            if (sum > rightSum) {
                rightSum = sum;
                maxRight = i;
            }
        }

        return new Result(maxLeft, maxRight, leftSum + rightSum);
    }

    private static Result maxSubArray(int[] A, int low, int high) {

        if (low == high) {
            return new Result(low, high, A[low]);
        }

        int mid = (low + high) / 2;

        Result leftSubArray = maxSubArray(A, low, mid);
        Result rightSubArray = maxSubArray(A, mid + 1, high);
        Result maxCrossingSubArray = maxCrossingSum(A, low, mid, high);

        int leftSum = leftSubArray.sum;
        int rightSum = rightSubArray.sum;
        int crossSum = maxCrossingSubArray.sum;

        if (leftSum > rightSum && leftSum > crossSum) {
            return new Result(leftSubArray.low, leftSubArray.high, leftSubArray.sum);
        } else if (rightSum > leftSum && rightSum > crossSum) {
            return new Result(rightSubArray.low, rightSubArray.high, rightSubArray.sum);
        } else {
            return new Result(maxCrossingSubArray.low, maxCrossingSubArray.high,
                maxCrossingSubArray.sum);
        }
    }

    public static class Result {

        public int low;
        public int high;
        public int sum;
        public Result(int low, int high, int sum) {
            this.low = low;
            this.high = high;
            this.sum = sum;
        }

    }

    /* Driver program to test maxSubArray */
    public static Result maxSubArray(int[] arr) {
        return maxSubArray(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String[] arrString = sc.nextLine().split(" ");

        int n = arrString.length;

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(arrString[i]);
        }

        Result result = maxSubArray(arr);

        int[] subArray = new int[result.high - result.low + 1];
        int j = 0;
        for (int i = result.low; i <= result.high; i++) {
            subArray[j++] = arr[i];
        }

        System.out.println(Arrays.toString(subArray));
        System.out.println("Sum : " + result.sum);
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

1.The implementation of Kadane's algorithm is wrong, it will fail on an array with some negative numbers. correct one should look like :

 public static void Kadane(int array[]) {
        int max_ending_here = 0;
        for (int i = 0; i < array.length; i++) {
            max_ending_here = Math.max(array[i], max_ending_here + array[i]);
            max_so_far = Math.max(max_so_far, max_ending_here);
        }
        System.out.println("Kadane(int array []): " + max_so_far);
    }

And many bugs in your code, like:

2.maxEndingHere should be initialized to 0 before you calculate the answer for:

[lowIndex,mid)
[mid, highIndex]
[lowCenter, highCenter]

now it only gets initialized before the first iteration.

3.lowCenter should be initialized to lowIndex

4.The program is unnecessarily long and complicated ... I don't know if i missed any more bugs...

Improve this answer

1 Comment

Your absolutely right regarding Kandane's algo for negative numbers, Im going to cleanup me coe and post the correct answer to D&C solution of max sub array

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.