Home >Backend Development >C#.Net Tutorial >Maximum sum of consecutive subsequences problem
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.