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

Maximum sum of consecutive subsequences problem

巴扎黑
Release: 2016-12-01 09:53:42
Original
1998 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.


Related labels:
source:php.cn
Statement of this Website
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
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template