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,end;
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] 超过当前 ans 就更新；若和相等但长度更长也要更新。关键是第二个空要判断‘和相等且当前段更长’，以及第三个空何时把 tmp 清零、beg 重置。

最容易把第二个空写成 tmp+a[i]>ans，这样会漏掉‘和相同但元素更多’的情况；或者把条件写成 tmp+a[i]>=ans，导致在 ans 没更新时错误地延长了长度。另外，beg 初始值若写成 1，后面 len=i-beg 就会少算一个元素，输出结果偏小。还有，第三个空如果误写成<=0，会把和为 0 的段也清零，导致后面无法正确拼接。

考点与思路

这道题考查最大连续子段和（Kadane 算法）的变体：在求出最大和的前提下，还要保证子段包含的元素个数最多。核心思路是维护三个变量：

• tmp：当前连续段的累加和（从 beg+1 到 i）；
• ans：全局最大和；
• len：对应 ans 的最长子段长度。

算法主线就是遍历数组，每读一个数 a[i]，先算 tmp+a[i]： 1. 如果它严格大于当前 ans，说明发现了新的最大和，立刻更新 ans 和 len（len = i - beg）； 2. 如果它等于 ans，但当前段长度 i - beg 比已记录的 len 长，也要更新 len； 3. 如果它小于 0，说明当前段已经变成负数，继续往后加只会拖累后面的和，此时要把 tmp 清零，并把 beg 重置为 i，让下一段从下一个元素重新开始。

逐空推导

① beg 的初值

beg 表示“当前段起始位置的前一位”。因为循环从 i=1 开始，第一段自然是从第 1 个元素起，所以起始位置的前一位是 0。若填 1，后面 len = i - beg 会少算一个元素，导致输出偏小。答案：0。

② else if 的条件

第一个 if 已经处理了 tmp+a[i] > ans 的情况。剩下的可能性只有两种：

• tmp+a[i] < ans：和变小，长度不变，直接跳过；
• tmp+a[i] == ans：和没变，但可能长度更长。

题目要求“在和最大的前提下还要求元素个数最多”，所以只有当和相等且当前段长度 i - beg 大于已记录的 len 时，才需要更新 len。因此第二个空要填 tmp+a[i] == ans（或等价写法 ans == tmp + a[i]）。注意不能写成 >=，否则在 ans 没更新的情况下也会误更新长度，导致逻辑错误。答案：tmp+a[i]==ans。

③ 重置 tmp 的条件

什么时候该把 tmp 清零？显然是当当前段累加和变成负数时，因为负数只会拉低后续的和。所以条件是 < 0。若写成 <= 0，会把和为 0 的段也清零，导致后面无法正确拼接（例如数列 4, -5, 3, 2, 4 中，4 + (-5) = -1 应该清零，但 3 + (-5) = -2 也要清零，而 0 本身不应清零）。答案：<0。

④ 重置 beg 的值

当 tmp+a[i] < 0 时，我们要丢弃当前段，让下一段从下一个元素开始。因为循环下一步会执行 i++，所以新的起始位置的前一位应该是当前的 i。若填 i+1，后面 len = i - beg 就会少算一个元素。答案：i。

⑤ 正常累加 tmp

在不满足重置条件时，要把当前元素加入 tmp。C++ 里常用 += 或 + 赋值，两者等价。答案：tmp+=a[i]（或 tmp=tmp+a[i]）。