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); | |
} | |
} |
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 thesum
is changed from 0 to positive. - End index should be updated to
i
when thesum
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hii you can check this implementation.
public class KadaneAlgorithm {
}