Created
September 4, 2012 18:44
-
-
Save arunma/3624849 to your computer and use it in GitHub Desktop.
Maximum sum Subarray problem - Kadane's algorithm - Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
@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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
First, maxSubSum() is quite simple when we do not need to know start and end index of the subarray.
Based on above, we know
i
when thesum
is changed from 0 to positive.i
when thesum
is increased.and the (start, end) index we want is when the
ans
is determined.Result in following code.
I think ashishs174's solution above is basically same with mine and compact.
But this is more understandable to me.