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
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...