最大连续子序列和问题
问题描述：给定一个序列a,a...a，求解其连续子序列中元素和的最大值例如： 6 -1 5 4 -7 这个序列最大连续子序列和为14
具体问题见： HDOJ 1003TZU 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; 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; 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+100int main(void){int n;int m;int a;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); thisSum += a; 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;}
程序主要部分还是上面的算法，只是加上了对子序列首尾索引号的处理。
页:
[1]