首页 > > 程序设计 > C/C++ >

最大连续子序列问题

2018-06-17 22:11:11来源：未知阅读 ()

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。
　　　　　　　　//这样合理性就很明显了。
	}    　　　　
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有