首页 > 代码库 > 杭电1003 Max Sum 【连续子序列求最大和】
杭电1003 Max Sum 【连续子序列求最大和】
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1003
题目意思:
即给出一串数据，求连续的子序列的最大和
解题思路:
因为我们很容易想到用一个max来存放找到的子序列的和中的最大值，通过不断比较，对max的值进行更新，最后我们就能够得到最大子序列的和，于是很容易想到用暴力搜索，见上一篇博客，这样的时间复杂度为O(n^3)，是超时的。
又因为想到只要一个数不是负数，不管它再小，加上去也是会使和变大的，所以我们需要用另一个变量来判断即将要加上的一个数是大于0还是小于0的，当它小于0的时候，就将sum归于0，又重新·判断。
像比如这一个例子
-1，5，-3，6，-7，和最大的子序列应该是（-1，5，-3，6，-7），之前困扰的是加到6就应该停止了，可是此时的sum不为0，应该怎样才能输得出最后的最大值呢，后来才想到（-1，5，-3，6）已经储存到max里面了，虽然此时的sum仍旧大于0，但是加上-7之后肯定比max小，所以sum的值的变化不会去影响max了，所以根本不用再考虑sum的值。
关键点————最大值始终是放在max里面的。
#include<stdio.h>int main(){ int ncase,a; long int num; int i; while(scanf("%d",&ncase)!=EOF) { int flag=1; while(flag<=ncase) { int sum=0; int max=-1001;//因为输入的值得范围在-1000到1000之间，所以令max为-1001 int beg=0,len=0,end=0; scanf("%ld",&num); for(i=1;i<=num;i++) { scanf("%d",&a); sum=sum+a; len++; if(sum>max) //max的值的更新 { beg=len; max=sum; end=i; } if(sum<0) { sum=0; len=0; } } printf("Case %d:\n",flag); printf("%d %ld %ld\n",max,end-beg+1,end); if(flag!=ncase) printf("\n"); flag++; } }}
杭电1003 Max Sum 【连续子序列求最大和】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。