Maximum sum of consecutive subsequences problem-C#.Net Tutorial-php.cn

Maximum sum of consecutive subsequences problem

巴扎黑

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

Original

1951 people have browsed it

Problem description: Given a sequence a[1], a[2]...a[n], find the maximum value of the sum of elements in its continuous subsequences
For example: 6 -1 5 4 -7 The maximum continuous value of this sequence The sum of the subsequences is 14
See the specific problem: HDOJ 1003 TZU 1202
This problem is also described in "Data Structure and Algorithm Analysis-C Language Description" (authored by Weiss) Chinese version on page 13 (English version on page 18). An algorithm program is given on page 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;  
}

Copy after login

I wrote the algorithm as follows:

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

Copy after login

At this time, the else keyword must be deleted, because different values are used for initialization caused by variables. The examples in the book can always ensure that MaxSum is non-negative. And the algorithm I rewrote will have a negative number MaxSum in many cases
My acm program is as follows (both websites above are 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;  
}

Copy after login

The main part of the program is still the above algorithm, just adding the pair sequence Processing of first and last index numbers.