Home » Arrays(Dont Mess With Me) » Kadane Algorithm

Kadane Algorithm

// this is KADANE ALGOL…
// 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


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 = sum + array[i];
 if (sum > maxsum)
 {
 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);
 }
}

Advertisements

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: