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

0

コードの問題は、(cumulativeSum>maxSum) が (Cumulative<0) の前にこれをチェックしており、maxSum が MIN であるため、最初の数値が負で 2 番目が正の場合、cumulativeSum> maxSum として失敗するため、-1 が追加されます。したがって、答えは 3 ではなく 2 になります。したがって、前に (cumulativeSum<0) をチェックするか、maxSum=-1 にするか、(cumulativeSum>maxSum &&cumulativeSum > 0) に条件を追加します。

于 2014-04-08T07:54:00.607 に答える
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 に答える