Home >Backend Development >C#.Net Tutorial >Maximum sum of consecutive subsequences problem

Maximum sum of consecutive subsequences problem

巴扎黑
巴扎黑Original
2016-12-01 09:53:421989browse

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

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

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


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


Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn