最大连续子序列和问题
程序员文章站
2022-04-10 10:38:18
...
问题描述:给定一个序列a[1],a[2]...a[n],求解其连续子序列中元素和的最大值
例如: 6 -1 5 4 -7 这个序列最大连续子序列和为14
具体问题见: HDOJ 1003 TZU 1202
这个问题在《数据结构与算法分析--c语言描述》(weiss著)中文版第13页(英文版第18页)中也有描述。在第21页给出了一个算法程序:
例如: 6 -1 5 4 -7 这个序列最大连续子序列和为14
具体问题见: HDOJ 1003 TZU 1202
这个问题在《数据结构与算法分析--c语言描述》(weiss著)中文版第13页(英文版第18页)中也有描述。在第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; }
我将算法写成了下面的样子:
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; }
此时必须将else这个关键字删除,这是因为使用了不同的值来初始化变量引起的。书本中的例子能够始终保证MaxSum为非负值。而我改写后的算法在很多情况下MaxSum都会是负数
我的acm程序如下(在上面两个网站都是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; }
程序主要部分还是上面的算法,只是加上了对子序列首尾索引号的处理。
上一篇: MVC框架的理解