Below is the code snippet: see that the maximum sum of sub array is 6 but it is getting calculated as 7.
So Kadane's algorithm is failing here?!

public class KadaneAlgo {

    public static void main(String[] args) {
        int maxSUm = maxSumSubArray(new int []{2,2,2,-2,-2,3,2});
        System.out.println(maxSUm); // prints 7
    }
    
    static int maxSumSubArray(int [] a){
        int size = a.length;
        int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

        for (int i = 0; i < size; i  )
        {
            max_ending_here = max_ending_here   a[i];
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
            if (max_ending_here < 0)
                max_ending_here = 0;
        }
        return max_so_far;
    }
}

CodePudding user response：

According to wiki, the correct answer is 7 so the code is correct.

Why? Because subarray also includes the min and max bounds of the array:

A[0..n] -> find subarray with bounds i,j where 0<=i<=j<=n; and in your case i=0 and j=6 (the whole array)

CodePudding user response：

There is nothing wrong with the code, the correct answer is 7 by adding all the numbers together.