I have the following implementation of Kadane's algorithm in java. It is basically to find the maximum sum of contiguous subarray.
String[] numbers = string.split(",");
int max_so_far = 0;
int max_ending_here = 0;
for (int i = 0; i < numbers.length-1;i++){
max_ending_here = max_ending_here + Integer.parseInt(numbers[i]);
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
System.out.println(max_so_far);
However this doesn't work if there is a combination of a negative and positive number in an array, for example the following:
2,3,-2,-1,10
Which should return a 12 as a maximum. As of now it returns 5
You algorithm implementation looks ok, but your loop conditional i < numbers.length-1
does not: it stops just 1 short of the end of the array. i < numbers.length
should do it :-)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With