Question: Given an array of integers(positive/negative) find a sub-array such that it gives max sum.
Solution(s):
Method 1: Using divide and conquer: Divide the given array in 2 sub-arrays from middle and find maximum sum in those sub-arrays.
case 1 : maximum sum is in left subarry
case 2 : maximum sum is in right subarry
case 3 : maximum sum may exist at the crossing point including both the sub-arrays Find the maximum from all these 3 cases that will give the maximum sum sub-array.
Method 2: Using Kadane's algorithm In this algorithm we scan the array and keep track of elements and based on the condition that either adding the current value will increment variable or not, we update the variables. Following program implements divide and conquer approach and Kadane's algorithm.
/**
* @author Vikky.Agrawal
*
*/
public class MaxSumSubArray {
int arr[];
MaxSumSubArray() {
arr = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
//arr = new int[] { -2, -1, -3, -4, -1, -2, -1, -5, -4 };
}
public static void main(String[] args) {
new MaxSumSubArray().operate();
}
public void operate() {
System.out.println("Max sum is " + findMaxSum(arr, 0, arr.length - 1));
System.out.println("Max sum using kadane's algo :"
+ findMaxSubArraySum(arr));
System.out.println("Alternate kadane's :"+findMaxSumKadane(arr));
}
//Method 1: divide and conquer
public int findMaxSum(int arr[], int low, int high) {
if (low == high) {
return arr[low];
}
int mid = (low + high) / 2;
return maxOfThree(findMaxSum(arr, low, mid),
findMaxSum(arr, mid + 1, high),
maxCrossSum(arr, low, mid, high));
}
//case 3: check whether max sum exist including crossing point.
public int maxCrossSum(int arr[], int low, int mid, int high) {
int leftSum = Integer.MIN_VALUE;
int rightSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= low; i--) {
sum = sum + arr[i];
if (sum > leftSum) {
leftSum = sum;
}
}
sum = 0;
for (int j = mid + 1; j <= high; j++) {
sum += arr[j];
if (sum > rightSum) {
rightSum = sum;
}
}
return leftSum + rightSum;
}
/**
* Method 2: Using Kadane's algorithm
* will return negative if all elements are negative
* Time complexity : O(n)
**/
public int findMaxSubArraySum(int arr[]) {
int max_ending_here = arr[0];
int max_so_far = arr[0];
int begin = 0;
int end = 0;
int temp = 0;
for (int i = 1; i < arr.length; i++) {
if (max_ending_here < arr[i]) {
max_ending_here = arr[i];
temp = i;
} else {
max_ending_here += arr[i];
}
if (max_ending_here >= max_so_far) {
max_so_far = max_ending_here;
begin = temp;
end = i;
}
}
System.out.println("Largest subarry start index :" + begin
+ " end index : " + end);
return max_so_far;
}
//Another approach using Kadane's algorithm
public int findMaxSumKadane(int arr[]){
int length=arr.length;
if(length==0){
return Integer.MIN_VALUE;
}
//This will help with negative numbers.
int max_ending_here =arr[0], max_so_far = arr[0];
for(int j=1; j<length; j++){
max_ending_here=maxOfTwo(max_ending_here+arr[j],arr[j]);
max_so_far= maxOfTwo(max_so_far, max_ending_here);
}
return max_so_far;
}
// Helper functions
public int maxOfTwo(int a, int b) {
return a > b ? a : b;
}
public int maxOfThree(int a, int b, int c) {
return maxOfTwo(maxOfTwo(a, b), c);
}
}
Complexity Analysis: For method 1(divide and conquer): it resembles to Master theorem case 2 hence time taken will be T(n)=2T(n/2)+O(n) = O(n logn)
For method 2: Kadane's algorithm makes only a single pass of the whole array hence time complexity will be O(n) which is linear and significant improvement than divide and conquer approach.
