August 30, 2012 · algorithms

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.

Kadane maximum sum subarray problem

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?