Maximum Sum Sub array

This is a interesting problem which can be solved in a variety of ways. This problem has a chunk of a chapter devoted in the Programming Pearls book by Jon Bentley.

Method 1. Brute Force O(n^2)

This involves taking each index i between 0 to len and for every other index j>i calculate the sum while keeping track of the maximum.

private static int sumbruteforce(int [] arr){
  int sum=0;
  int max=Integer.MIN_VALUE;
  int maxi=0;
  int maxj=0;
  for(int i=0;i<arr.length;i++){
   sum=0;
   for(int j=i;j<arr.length;j++){
    sum+=arr[j];
    if(sum>max){
     max=sum;
     maxi=i;
     maxj=j;
    }
   }  
  }
  System.out.println(maxi+" "+maxj);
  return max;
 }

2. Method 2: Divide and Conquer: O(n log n)
This involves dividing the array recursively into 3 parts left, right and mid. And comparing max sum of the three.

Calculating max(left) and max(right) is trivial using recursion. For the mid element, we know the left bound (l) lies in left half and right bound (r) lies in right half. So we calculate l s.t sum of elements between l and mid is max and r s.t the sum is maximum for elements between mid and right.

private static int sumDivConquer(int [] arr, int l, int h){
  if(l>h)
   return 0;
  if(l==h)
   return arr[l];

  
  int m=(int) Math.floor((double)((l+h)/2));
  int max=0;
  
  max=sumDivConquer(arr, l, m);
  max=Math.max(max,sumDivConquer(arr, m+1, h));
  
  
  int L=0;
  int R=0;
  int S=0;
  for(int i=m;i>=l;i--){
   S+=arr[i];
   L=S>L? S:L;
  }
  R=S=0;
  for(int i=m+1;i<=h;i++){
   S+=arr[i];
   R=S>R? S:R;
  }
  max=Math.max(max, L+R);
  
  return max;     
 }

3. Dynamic programming O(n)

An optimized DP solution takes O(n).

The naive DP solution acts exactly like method 1 and generates a matrix A[i,j] containing sum of elements with left bound i and right bound j.

The optimized DP constructs a single dimension table of array size, with
table[i]: Represents the sum of subarray with maximum sum terminating at i;

for i=0, table[0]=arr[0]
for i>0, table[i]= Max{ arr[i], arr[i]+table[i-1]}

Once we have the table finding max sum takes only a single pass through the above table, we can fasten the procedure up by keeping track of max side by side.

private static int sumDP(int [] arr){
 int table[]=new int[arr.length];
 table[0]=arr[0];
 for(int i=1;i<arr.length;i++){
  table[i]=Math.max(arr[i], arr[i]+table[i-1]);
 }
 int max=Integer.MIN_VALUE;
 for(int i=0;i<arr.length;i++){
  if(table[i]>max)
   max=table[i];
 }
 return max;
}
 

A simpler algorithm based on the same idea as the DP method is called Kadane's algorithm and it works without the need of maintaining the auxiliary table.

The code is derived from here

private static int sumKadane(int arr[]){
    int max=Integer.MIN_VALUE;
    int a,b; a=b=0;
    int curr = 0;
    int aa = 1;
    for (int bb= 1;bb<arr.length;bb++){
        curr = curr + arr[bb];
        if (curr > max) {
            max=curr;
            a=aa;
            b=bb;             
        }
        
        if (curr < 0) {
            curr = 0;
            aa = bb + 1;
        }
    }
    System.out.println(a+" "+b);
    return max;
}