I have written Kadane's algorithm but somehow it returns incorrect result. Not sure why. Here is the implementation. It is basically to find the `ubarray with maximum sum in an array
public class Kadane {
public static void main(String[] args) {
int[] arr = {-2, -5, 6, -2, -3, 1, 5, -6};
Kadane k = new Kadane();
System.out.println(k.calculate(arr, 0, 0));
}
public int calculate(int[] arr, int pointer, int sum) {
if(pointer >= arr.length )
return sum;
return Math.max(calculate(arr, pointer+1, sum+arr[pointer]), calculate(arr, pointer+1, 0));
}
}
I suppose it should somehow return the max sum which is 7. In the computation I see 7 being calculated but it return 1. Is there any fundamental thing I am missing in the code?
I have read other implementations and they make sense as well, just not getting my head around on why is it not returning the correct answer.
Thanks in advance!
You are not accounting for the fact that you may have already found the sum you want. Thus, you need:
return Math.max(sum, Math.max(calculate(arr, pointer+1, sum+arr[pointer]), calculate(arr, pointer+1, 0)));