javaalgorithmkadanes-algorithm

Kadane algorithm implementation returns incorrect result


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!


Solution

  • 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)));