-
-
Save arunma/3624849 to your computer and use it in GitHub Desktop.
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); | |
} | |
} |
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 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
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;
}