Maximum sum Subarray problem - Kadane's algorithm - Java

Kadane.java

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);
    }
   
}

Hi
I think your algo has some defects,
try this: {-6,2,-3,-4,-1,-5,-5};

you should not put a else if there, instead, put another if
if (cumulativeSum<0){
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}

Agree with Manyan. Your code doesn't work if input array starts with negative numbers. Another counter example is {-1, 2, 3, -3, 4}.

Yes. There can be one more tweak.

Change
int maxSum = Integer.MIN_VALUE;
to
int maxSum = 0;

Hii you can check this implementation.

public class KadaneAlgorithm {

int max_so_far=0;
int max_ending_here=0;
int []a;
public KadaneAlgorithm(int [] a) {
    this.a=a;
}

public int solution(){

    int s=0;int e=0;boolean f=false;
    for (int i = 0; i <a.length; i++) {

        if (max_ending_here+a[i]>0) {

            max_ending_here=max_ending_here+a[i];

            if (max_so_far<max_ending_here) {
                max_so_far=max_ending_here;
                if (!f) {
                    s=i;
                    f=true;
                }
                e=i;
            }
        }

    }
    System.out.println("Position in array :(" + s +","+e+")");
    return max_so_far;

}

public static void main(String[] args) {
    int a[]={-2,-3,4,1,-2,1,5,-3}; // change it with your input array
    //int a[] = {-6,2,-3,-4,-1,-5,-5};
    //int a[]={-1,2,3,-3,4};

    KadaneAlgorithm sdf = new KadaneAlgorithm(a);
    System.out.println(sdf.solution());
}

}

not correct
check with a[]={-7,-8,-6,-9,-10} input

First, maxSubSum() is quite simple when we do not need to know start and end index of the subarray.

    public static void maxSubSum(int[] a) {
        int ans = 0; // max of sum
        int sum = 0; // max sum of subarray ending i (including empty)
        for (int i = 0; i < a.length; i++) {
            sum = Math.max(sum + a[i], 0);
            ans = Math.max(ans, sum);
        }
        System.out.println(ans);
    }

Based on above, we know

• Start index should be set to i when the sum is changed from 0 to positive.
• End index should be updated to i when the sum is increased.

and the (start, end) index we want is when the ans is determined.
Result in following code.

    public static void maxSubSumWithRange(int[] a) {
        int ans = 0; // no selection. And I will not select subarray of 0s as max sub sum
        int ansStart = -1; // (-1, -1) no selection, or a inclusive subarray indices
        int ansEnd = -1;

        int sum = 0; // max sum of subarray ending i (including empty)
        int start = -1;
        int end = -1;

        for (int i = 0; i < a.length; i++) {
            int sumSaved = sum;
            sum = Math.max(sum + a[i], 0);
            if (sumSaved == 0 && sum > 0)
                start = i;
            if (sum > sumSaved)
                end = i;
            ans = Math.max(ans, sum);
            if (ans == sum) { // last for tie
                ansStart = start;
                ansEnd = end;
            }
        }
        System.out.println(ans + " (" + ansStart + ", " + ansEnd + ")");
    }

I think ashishs174's solution above is basically same with mine and compact.
But this is more understandable to me.

@veshboo it won't work for an array with all negative numbers : {-6,-9,-3,-5-2}

Check this solution in Python : Kadane.py

This code overworked. Commentators have left the wrong options. They do not consider negative numbers, did not read the problem carefully on Wikipedia. Working easy example:

  /**
  * Kadane 1d
  * @return max sum
  */
  public static int maxSum(int[] a) {
    int result = a[0]; //get first value for correct comparison
    int sum = a[0];
    for (int i = 1; i < a.length; i++) {
      sum = Math.max(sum + a[i], a[i]); //first step getting max sum, temporary value
      result = Math.max(result, sum);
    }
    return result;
  }

  /**
  * Kadane 2d
  * @param array
  * @return max sum
  */
  public static int maxSum2D(int array[][]){
    int result = Integer.MIN_VALUE; //result max sum
    for (int i = 0; i < array.length; i++) {
      int sum = maxSum(array[i]);
      result = Math.max(result, sum);
    }
    return result;
  }

Supplemented, with indexes:

  /**
  * @param zeroNegative true - return 0 or positive result
  */
  public static SumData maxSum(int[] a, boolean zeroNegative) {
    int result = a[0]; //get first value for correct comparison
    int sum = a[0];
    int start = 0, end = 0;
    for (int i = 1; i < a.length; i++) {
      //sum = Math.max(sum + a[i], a[i]); //first step getting max sum, temporary value
      int newSum = sum + a[i]; //new sum
      if (newSum > a[i]) { //get max sum
        sum = newSum;
      } else {
        sum = a[i];
        start = i;
        end = i;
      }
      if (sum > result) { //save current max sum;
        end = i;
        result = sum;
      }
    }
    if (zeroNegative && result < 0) result = 0;
    return new SumData(start, end, result);
  }
 
  /**
  * @param array
  * @param useLength true - use length least value, false - use summands least value for get index
  * @param zeroNegative true - return 0 or positive result
  * @return key - index in array with max sum, value - SumData for found subarray
  */
  public static Entry<Integer, SumData> maxSum2D(int array[][], boolean useLength, boolean zeroNegative){
    int lastIndex = 0; //index with max sum
    int lastMax = Integer.MIN_VALUE; //max sum
    int lastLength = 0; //last array[i].length or summands, for get index with the least value (length or summands)
    SumData maxData = null; //current max sum data
    for (int i = 0; i < array.length; i++) {
      SumData data = maxSum(array[i], zeroNegative); //get sum and other data for subarray
      int newLength = useLength ? array[i].length : data.SUMMANDS; //use length or summands
      if (data.SUM == lastMax && newLength <= lastLength) { //save index with the least value (length or summands)
        lastIndex = i;
        maxData = data;
      } else if (data.SUM > lastMax) { //update index and max sum value
        lastIndex = i;
        lastMax = data.SUM;
        maxData = data;
      }
      lastLength = newLength; //save length or summands for use next iteration
    }
    return new SimpleEntry<>(lastIndex, maxData);
  }

Fully:

• Easy: https://pastebin.com/Qu1x0TL8
• Supplemented: https://pastebin.com/Tjv602Ad
• With indexes: https://pastebin.com/QsgPBfY6