c++ - 这是 Kadane 算法的错误实现吗？

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

我怀疑是否给出了 here 的实现是否正确，所以我完全用 C++ 实现了它，对于上面的测试用例，它不起作用。找不到算法哪里错了？

Answer 1

拿int maxSum = -1; 会解决您的问题。你上面的程序也是不可编译的。这适用于 integer 数字

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