这是卡达内算法的错误实现吗？

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

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

Answer 1

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

Answer 2

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

这是你的问题。你在骗算法。在索引0处开始和结束的子数组的和为arr[0]，而不是负无穷大。但这也不是一个好的起点。

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

任何数组都有一个零和子数组：一个空的。你需要打败那个，而不是任何负和。

Answer 3

总的来说，有很多好的资源。这里有一个链接，指向一个您应该在C++中查找的有用资源。您还可以查看此资源，它是下面代码的来源，并且具有C实现。以下是粗略算法的伪代码：

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

下面是一个用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 %dn", max_sum);
   getchar();
   return 0;
}

正如人们所指出的，这种方法并不适用于所有的负数。如果所有数字都为负数，它只返回0。因此，我们可以进一步优化问题。以下是一些很好地优化了原始方法的示例代码：

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

您的代码的问题是，您在(CucumulativeSum>maxSum(之前检查了这个(Cucument<0(，因为您的maxSum是MIN，所以如果第一个数字是负数，第二个数字是正数，那么它将失败，因为cumulativeSum>maxSum，所以-1将被添加到累积总和中，因此答案将是2而不是3。因此，在之前检查(cumulativeSum<0(，或者使maxSum=-1，或者在(accumulativeSum>maxSum&&cumulativeSum>0(中添加条件