Skip to content

Instantly share code, notes, and snippets.

@arunma
Created August 29, 2012 16:29
Show Gist options
  • Save arunma/3515263 to your computer and use it in GitHub Desktop.
Save arunma/3515263 to your computer and use it in GitHub Desktop.
Kadane's maximum sum subarray algorithm
/*Note : This code fails for inputs such as int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 };
A modified version of this program is available at gist: https://gist.github.com/gists/3624849
This program is retained for archival purposes.
*/
public class Kadane {
public static void main(String[] args) {
int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
findMaxSubArray(intArr);
}
public static void findMaxSubArray(int[] inputArray){
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = Integer.MIN_VALUE;
int sum= 0;
for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
int eachArrayItem = inputArray[currentIndex];
sum+=eachArrayItem;
if( eachArrayItem > sum){
maxStartIndex = currentIndex;
sum = eachArrayItem;
}
if(sum>maxSum){
maxSum = sum;
maxEndIndex = currentIndex;
}
}
System.out.println("Max sum : "+maxSum);
System.out.println("Max start index : "+maxStartIndex);
System.out.println("Max end index : "+maxEndIndex);
}
}
@arunma
Copy link
Author

arunma commented Aug 29, 2012

This code is part of the blog located at http://octopress.dev/blog/2012/08/30/maximum-continuous-subarray-problem-kandanes-algorithm/. There is an accompanying presentation to this code.

@ashimasingla20
Copy link

the code given in example {3, -1, -1, -1, -1, -1, 2, 0, 0, 0 } does not give a correct output
Max sum : 3
Max start index : 6
Max end index : 0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment