NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 27 题

完善程序： （最大连续子段和） 给出一个数列（元素个数不多于 $100$），数列元素均为负整数、正整数、$0$。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为$4,-5,3,2,4$ 时，输出 $9$ 和 $3$；数列为 $1,2,3,-5,0,7,8$ 时，输出 $16$ 和 $7$。

#include <iostream>
using namespace std;

int a[101];
int n,i,ans,len,tmp,beg;

int main(){
	cin >> n;
	for (i=1;i<=n;i++)
		cin >> a[i];
	tmp=0;
	ans=0;
	len=0;
	beg= [    ①    ] ;
	for (i=1;i<=n;i++){
		if (tmp+a[i]>ans){
			ans=tmp+a[i];
			len=i-beg;
		}
		else if ( [       ②        ] &&i-beg>len)
			len=i-beg;
		if (tmp+a[i] [   ③   ]  ){
			beg=   [  ④    ] ;
			tmp=0;
		}
		else
		[	   ⑤        ];
	}
	cout << ans << " " << len << endl;
	return 0;
}

这题是最大连续子段和的变体，核心在于 Kadane 算法的贪心策略：维护当前段和 tmp，遇到 tmp+a[i] 变大就更新答案，变负就果断重置。填空时注意 beg 的初始值、等和时比较长度、以及重置后 tmp 如何继承当前元素。

最容易栽跟头的是 beg 的初始化，很多学生写成 1 导致长度计算偏移；其次是等和时忘记判断长度，只更新 ans 却丢了更长序列；还有重置逻辑，有的写成 tmp=0 后没把 a[i] 加进去，导致下一轮 tmp 从 0 开始，完全丢失当前元素的贡献；另外 tmp+a[i]<0 时直接重置 beg 是对的，但别忘了此时 tmp 要清零，否则后续累加会出错。

完善程序 - 最大连续子段和（NOIP 普及组 2009 第 27 题）

这题考什么

这道题考查的是最大连续子段和问题，也就是经典的 Kadane 算法思想。题目要求找出一个连续子数列，使得元素之和最大；如果和相等，则选长度最长的。输出最大和以及对应的长度。