連続部分列の最大和問題-C#.Net チュートリアル-php.cn

連続部分列の最大和問題

巴扎黑

リリース： 2016-12-01 09:53:42

オリジナル

1952 人が閲覧しました

問題の説明: シーケンス a[1]、a[2]...a[n] が与えられた場合、その連続サブシーケンス内の要素の合計の最大値を見つけます
例: 6 -1 5 4 -7 このシーケンス最大の連続値を持つ部分列の合計は 14 です
具体的な問題については、HDOJ 1003 TZU 1202 を参照してください
この問題は、「データ構造とアルゴリズムの解析 - C 言語の記述」(Weiss 著) 中国語版でも説明されています13 ページ (英語版は 18 ページ)。アルゴリズムのプログラムは 21 ページに記載されています。

int MaxSubsequenceSum(const int A[], int N)  
{  
  int ThisSum,MaxSum,j;  
  ThisSum = MaxSum = 0;  
  for(j = 0; j < N; j++)  
  {  
    ThisSum += A[j];  
    if(ThisSum > MaxSum)  
      MaxSum = ThisSum;  
    else if(ThisSum < 0)  
      ThisSum = 0;  
   }  
  return MaxSum;  
}

ログイン後にコピー

私は次のようにアルゴリズムを書きました:

int MaxSubsequenceSum(const int A[], int N)  
{  
  int ThisSum,MaxSum,j;  
  ThisSum =0， MaxSum =INT_MIN;  
  for(j = 0; j < N; j++)  
  {  
    ThisSum += A[j];  
    if(ThisSum > MaxSum)  
      MaxSum = ThisSum;  
    if(ThisSum < 0)  
      ThisSum = 0;  
   }  
  return MaxSum;  
}

ログイン後にコピー

このとき、変数による初期化に異なる値が使用されるため、else キーワードを削除する必要があります。この本の例では、常に MaxSum が負でないことを確認できます。そして、私が書き直したアルゴリズムは、多くの場合、負の数の MaxSum を持ちます
私の acm プログラムは次のとおりです (上記の Web サイトはどちらも ac です):

#include <stdio.h>  
#include <limits.h>  
  
#define MAX 100000+100  
  
int main(void)  
{  
  int n;  
  int m;  
  int a[MAX];  
  int i,j;  
  int thisSum,maxSum;  
  int maxStart,maxEnd,thisStart;  
  
  scanf("%d",&n);  
  for(i = 1; i <= n; i++)  
    {  
      scanf("%d",&m);  
      for(maxStart=maxEnd=thisStart=thisSum=0,maxSum=INT_MIN,j = 0; j < m; j++)  
    {  
      scanf("%d",&a[j]);  
      thisSum += a[j];  
  
      if(thisSum > maxSum)  
        {  
          maxSum = thisSum;  
          maxStart = thisStart;  
          maxEnd = j;  
        }  
      if(thisSum < 0)  
        {  
          thisSum = 0;  
          thisStart = j+1;  
        }  
    }  
      if(i > 1)  
    printf("\n");  
      printf("Case %d:\n",i);  
      printf("%d %d %d\n",maxSum,maxStart+1,maxEnd+1);  
    }  
  return 0;  
}

ログイン後にコピー

プログラムの主要部分は依然として上記のアルゴリズムであり、ペアシーケンスを追加するだけです最初と最後のインデックス番号の処理。