Description

给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ...,
Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,
例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和
为20。要求编写程序得到最大和。

output

最大连续子序列的和。

核心代码如下

 

int ans=0,now=0;
for(int i=0;i<n;i++){//代码很简单,解释下它的合理性吧
    now+=a[i];
    if(now<0)//如果当前值已经小于0了,假设它的后面那一串数字和是正数,一个正数加一个负数和必然变小,说明从这个a[i]开始包括它之前的所有数都可以不要了。
    now=0;//舍去前面的所有数的和。
    else{
        if(now>ans)
        ans=now;//最后要输出的是最大值每次加一个数所得的和都和ans比较一次,
    			//循环结束ans得到的一定是最大的。
				// 3 -5 2 4 -7 -5 1 对于这组样例,当加到-5时和小于0,所以前面这一小段3 -5
				//就没有用处了,现在ans=3,再+2,2<3,ans还是=3,再+4,6>3,ans变为6,之后
        //在+(-7)now<0,now=0,再+(-5)now还是<0,now在变为=0,最后再加1,1<6
        //根本不会影响ans,ans依然保持在最大值6。
        //这样合理性就很明显了。
	}        
}

 

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!