0 
#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++ 实现了它，而对于上面的测试用例，它不起作用。我找不到算法错误的地方？

4

4 回答 4

1

Take 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 ; 
}
于 2014-04-08T05:03:58.073 回答
0 
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = MIN;

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

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

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

于 2014-04-08T05:30:06.820 回答
0

一般来说，那里有很多好的资源。这是一个有用资源的链接，您应该查看 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 %d\n", 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;
}
于 2014-04-08T06:01:48.400 回答
0

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

于 2014-04-08T07:54:00.607 回答