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

### Like this:

Like Loading...

*Related*

//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++;

}

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;

}

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:

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.