Is this an incorrect implementation of Kadane's algorithm?

Question

#include <iostream>
#include <limits>
int MIN = std::numeric_limits<int>::min()
using namespace std ; 

void findMaxSubArray(int inputArray[] , int n )
{

int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = MIN ; 

int cumulativeSum= 0;
int maxStartIndexUntilNow=0;

for (int currentIndex = 0; currentIndex < n ; 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;
    }
}

cout << "Max sum         : "<< maxSum << "\n" ;
cout << "Max start index : "<< maxStartIndex << "\n" ;
cout << "Max end index   : "<< maxEndIndex << "\n" ;
}

int main() 
{
    int intArr[] = {-1,3,-1,-1,-1,-1,-1,-1 } ;
    //int intArr[] = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
    //int intArr[]={-6,-2,-3,-4,-1,-5,-5};
    findMaxSubArray(intArr,8);
    return 0 ; 
}  

I was skeptical about whether the implementation given here was correct or not so I implemented it exactly in C++ and for the above test case it doesn't work. I can't find out where the algorithm is wrong?

Answer 1

Take int maxSum = -1; would solve your problem. also your above program is not compilable . This works for integer numbers

#include <iostream>
#include <limits>
using namespace std ; 

int MIN = std::numeric_limits<int>::min();
void findMaxSubArray(int inputArray[] , int n )
{

    int maxStartIndex=0;
    int maxEndIndex=0;
    int maxSum = -1 ; 

    int cumulativeSum= 0;
    int maxStartIndexUntilNow=0;

    for (int currentIndex = 0; currentIndex < n ; 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;
        }
    }

    cout<< "Max sum         : "<< maxSum << "\n" ;
    cout<< "Max start index : "<< maxStartIndex << "\n" ;
    cout<< "Max end index   : "<< maxEndIndex << "\n" ;
}

int main() 
{
    int intArr[] = {-1,3,-1,-1,-1,-1,-1,-1 } ;
    //int intArr[] = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
    //int intArr[]={-6,-2,-3,-4,-1,-5,-5};
    findMaxSubArray(intArr,8);
    return 0 ; 
}  

Answer 2

int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = MIN;

This is your problem. You are lying to the algorithm. A subarray that starts and ends at index 0 has a sum of arr[0], not negative infinity. But that's not a good starting point either.

int maxStartIndex=0;
int maxEndIndex=-1;
int maxSum = 0;

Any array has a zero-sum subarray: an empty one. You need to beat that one, not any negative sum.

Answer 3

In general, there are lots of good resources out there. Here is a link to a useful resource that you should look at for C++. You can also look at this resource which is where the code below originates from and which has a C implementation. Here is the pseudo-code for the rough algorithm:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

Here is a simple program that implements the algorithm in C:

#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
   int max_so_far = 0, max_ending_here = 0;
   int i;
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
     if(max_ending_here < 0)
        max_ending_here = 0;
     if(max_so_far < max_ending_here)
        max_so_far = max_ending_here;
    }
    return max_so_far;
} 

/*Driver program to test maxSubArraySum*/
int main()
{
   int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   printf("Maximum contiguous sum is %d\n", max_sum);
   getchar();
   return 0;
}

As people have noted, this approach doesn't work for all negative numbers. It simply returns 0 if all numbers are negative. We can thus further optimize the problem. Here is some sample code that nicely optimizes the original approach:

int maxSubArraySum(int a[], int size)
{
   int max_so_far = 0, max_ending_here = 0;
   int i;
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
     if(max_ending_here < 0)
         max_ending_here = 0;

     /* Do not compare for all elements. Compare only   
        when  max_ending_here > 0 */
     else if (max_so_far < max_ending_here)
         max_so_far = max_ending_here;
   }
   return max_so_far;
}

Answer 4

The issue with your code is you are (cumulativeSum>maxSum) checking this before (Cumulative<0) and as your maxSum is MIN so if first number is negative and second is positive it will fail as cumulativeSum> maxSum so -1 will be added to cumulativeSum and hence answer would be 2 not 3. Therefore either check for (cumulativeSum<0) before or make maxSum=-1 or add condition in (cumulativeSum>maxSum && cumulativeSum > 0)