Problem mit der maximalen Summe aufeinanderfolgender Teilsequenzen-C#.Net-Tutorial-php.cn

Problem mit der maximalen Summe aufeinanderfolgender Teilsequenzen

巴扎黑

Freigeben： 2016-12-01 09:53:42

Original

1952 Leute haben es durchsucht

Problembeschreibung: Finden Sie bei einer gegebenen Sequenz a[1],a[2]...a[n] den Maximalwert der Summe der Elemente in ihren aufeinanderfolgenden Teilsequenzen
Zum Beispiel: 6 -1 5 4 -7 Die maximale kontinuierliche Teilsequenzsumme dieser Sequenz beträgt 14
Spezifische Fragen finden Sie unter: HDOJ 1003 TZU 1202
Diese Frage ist in „Data Structure and Algorithm Analysis – C Language Description“ (geschrieben von Weiss) auf Chinesisch Version Seite 13 (englische Version) Auch auf Seite 18 beschrieben). Ein Algorithmusprogramm finden Sie auf Seite 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;  
}

Nach dem Login kopieren

Ich habe den Algorithmus wie folgt geschrieben:

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

Nach dem Login kopieren

Zu diesem Zeitpunkt Das Schlüsselwort else muss gelöscht werden, da zum Initialisieren der Variablen unterschiedliche Werte verwendet werden. Die Beispiele im Buch können immer sicherstellen, dass MaxSum nicht negativ ist. In dem von mir neu geschriebenen Algorithmus ist MaxSum in vielen Fällen negativ.
Mein ACM-Programm lautet wie folgt (beide Websites oben sind 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;  
}

Nach dem Login kopieren

Der Hauptteil des Programms ist immer noch Wie oben Der Algorithmus fügt nur die Verarbeitung der ersten und letzten Indexnummern der Teilsequenz hinzu.