ISourceCode

Make the frequent cases fast and the rare case correct

For a given array of integers (positive and negative) find the largest sum of a contiguous sequence – Kadane’s Algorithm

The Aim of the program as the title suggest is to find the largest sum of a contiguous sequence of array elements..(array containing at least one positive number)
For example
Array {4,-9,3,-2,4,-12} the sequence {3,-2,4} is the continuous sequence with largest sum 5

This algorithm was solved by Jay Kadane of CMU in linear time. Earlier this problem was posed by Ulf Grenander of Brown University. Actually called “Maximum subarray problem”

Crux of the Kadane’s algorithm is to search for all positive contiguous subarrays of the array and keep track of maximum sum contiguous segment among all positive subarrays.This algo is a simple example of dynamic programming as it makes use of optimal substructure . The maxsum obtained at each array index is calculated by overlapping subproblem i.e the previous sum obtained for previous array index [maxsum=sum].

import java.io.*;
public class MaxSubsum
{	
	public static int MaxSum(int[] array) {
	int maxsum = 0;
	int sum = 0;
	for (int i = 0; i < array.length; i++) 
	{
		sum += array[i];
		if (maxsum < sum) 
		{
			maxsum = sum;
		} 
		else if (sum < 0) 
		{
			sum = 0;
		}
	}
	return maxsum;
	}
	public static void main (String[] args) throws IOException
	{
		int[] a=new int[25];
		int num=0,i=0;		
		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Enter the Number of element");
		num=Integer.parseInt(reader.readLine());
		System.out.println("Enter the array");
		for(i=1;i<=num;i++)
		{
			a[i]=Integer.parseInt(reader.readLine());
		}
		int value = MaxSum(a);
		System.out.println("The maximum sub sum is:"+value);
	}
}

OUTPUT:
laptop:~/code$ java MaxSubsum
Enter the Number of element
6
Enter the array
4
-9
3
-2
4
-12
The maximum sub sum is:5

In this algorithm for the case where all the numbers in the array are negative, the max sum is zero ( assumption made). However based on requirement the algorithm can be modified to find largest sum with all elements being negative numbers.In such a case for {-1,-5,-7} the sum will be -1.

Kadane’s algo for 2-D array runs in O(n^3) and implemented here

More about this at Wikipedia

In a future post i will take a look at extracting the exact array elements that constitute the sum.Perhaps i will make an addition to this article itself

Thanks for reading

4 responses to “For a given array of integers (positive and negative) find the largest sum of a contiguous sequence – Kadane’s Algorithm

  1. Amit Veerani July 23, 2012 at 7:52 am

    //The only Challenge in this problem was to print start and end indices

    public static int findMaxSubArray(int[] array)
    {
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
    while(i<array.length)
    {
    if(cumulativeSum+array[i]max)
    {
    max=cumulativeSum;
    savepoint=start;
    end=i;
    }
    i++;
    }

  2. Amit Veerani July 23, 2012 at 7:52 am

    public static int findMaxSubArray(int[] array)
    {
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
    while(i<array.length)
    {
    if(cumulativeSum+array[i]max)
    {
    max=cumulativeSum;
    savepoint=start;
    end=i;
    }
    i++;
    }

    System.out.println(“Max : “+max+” Start indices : “+savepoint+” end indices : “+end);
    return max;

    }

  3. Kenneth Q. Yang September 12, 2012 at 2:02 pm

    This implementation only works if a positive sum of of sub array exists, it won’t work otherwise, for example, serious of negative numbers, here is the implementation that calculate the starting ending index in addition to the sum:

    	
    	 /* this method only works for positive numbers, or at least not working for
    	  * all negative numbers
    	 */
    	public static int maxSubarray(int[] a) {
    
    		int max_so_far = 0;
    		int max_ending_here = 0;
    
    		if (a.length == 1)
    			return a[0];
    
    		for (int i = 0; i < a.length; i++) {
    			max_ending_here = Math.max(0, max_ending_here + a[i]);
    			max_so_far = Math.max(max_so_far, max_ending_here);
    		}
    
    		return max_so_far;
    
    	}
    
    	/* by Ken Q. Yang
    	 * This method works for negatives numbers as well, return array of max
    	 * result, starting index, ending index
    	 */
    	public static int[] maxSumSubArray(int[] data) {
    		int maxSum = Integer.MIN_VALUE;
    		int curSum = 0;
    		int a = 0;
    		int b = 0;
    		int s = 0;
    		int i = 0; // loop index
    		for (i = 0; i  maxSum) {
    				maxSum = curSum;
    				a = s;
    				b = i;
    			}
    			if (curSum < 0) {
    				// if curSum < 0, it means current element data[i] is a big negative which is larger than previous curSum,
    				// so this big negative got to be out of equation of calculating max sub array, got start from different index
    				curSum = 0;
    				s = i + 1;
    			}
    		}
    
    		return new int[] { maxSum, a, b };
    	}
    
    • chinmaylokesh September 12, 2012 at 2:15 pm

      Thanks yours is a solution to a slight variation of the proble =m statement.

      You are right, but for Kadane algorithm or the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum.

      Kadane’s Algorithm requires at least one positive number.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: