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 ; 
}