# Find Continuous subarray with maximum sum problem - Kadane's algorithm

**Update :***Previous version of the code failed for some inputs, as pointed out by @Thinker in the first comment. Changes to the program and the presentation were made. Tested to satisfy most conditions that I could google for.*

In a desperate attempt to increase my sad looking stackoverflow reputation, I replied to an old but interesting problem.

The problem goes like this :

Given `Random integers in array. Find the greatest sum of a continuous subset`

The problem is otherwise known as the Maximum subarray problem and is beaten to death numerous times.

So, instead of just translating a Python program into Java, I decided to pull together some slides which explains how this algorithm works.

And to bore you to death, here is the Java version of the modified algorithm :

```
package me.rerun;
public class Kadane {
public static void main(String[] args) {
int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 };
//int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
//int[] intArr={-6,-2,-3,-4,-1,-5,-5};
findMaxSubArray(intArr);
}
public static void findMaxSubArray(int[] inputArray){
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = Integer.MIN_VALUE;
int cumulativeSum= 0;
int maxStartIndexUntilNow=0;
for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
int eachArrayItem = inputArray[currentIndex];
cumulativeSum+=eachArrayItem;
if(cumulativeSum>maxSum){
maxSum = cumulativeSum;
maxStartIndex=maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
else if (cumulativeSum<0){
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}
}
System.out.println("Max sum : "+maxSum);
System.out.println("Max start index : "+maxStartIndex);
System.out.println("Max end index : "+maxEndIndex);
}
}
```

Rajesh was kind enough to write the implementation in Scala. Sweet huh?