问题描述：给定一个序列a[1],a[2]…a[n]，求解其连续子序列中元素和的最大值
例如： 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 MaxSum) MaxSum = ThisSum; else if(ThisSum 我将算法写成了下面的样子：
int MaxSubsequenceSum(const int A[], int N) { int ThisSum,MaxSum,j; ThisSum =0， MaxSum =INT_MIN; for(j = 0; j MaxSum) MaxSum = ThisSum; if(ThisSum 此时必须将else这个关键字删除，这是因为使用了不同的值来初始化变量引起的。书本中的例子能够始终保证MaxSum为非负值。而我改写后的算法在很多情况下MaxSum都会是负数
我的acm程序如下（在上面两个网站都是ac）：
#include #include #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 maxSum) { maxSum = thisSum; maxStart = thisStart; maxEnd = j; } if(thisSum 1) printf(""); printf("Case %d:",i); printf("%d %d %d",maxSum,maxStart+1,maxEnd+1); } return 0; }
登录后复制
程序主要部分还是上面的算法，只是加上了对子序列首尾索引号的处理。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2445460.html
