2026杭电春季赛热身赛-1007最大三段和（kadane算法）

春天来了，我们可以在各处看到盛开的花朵，多么美丽！而各个程序设计竞赛也将如这些花一样接踵而至。为了进一步提升程序设计能力，就让我来记录一下杭电赛的学习吧！今天的这道题主要记录kadane算法的学习，这道题便是前两天新鲜出炉的热身赛题目！

题目

Problem Description

木木同学最近做了一道最大子段和，感觉很有意思，然后想了一下如果取两段呢？他很快就会了。那如果取三段呢？木木同学学艺不精没想出来，于是便来请教你了。

给出一个长度为 n 的序列 a，要求从中选出三个子段，使得这三个子段的所有数字和最大。每个子段的长度至少为1，并且 两个子段之间至少间隔一个数，同时要求第二个子段长度为1。

Input

Output&Sample

题解

思考

对于单一的最大子段和问题，很好去解决，只要找到差值最大的前缀和就可以了。而最大三段和似乎就有些棘手了。这道题有一个条件：第二个子段的长度为1。这样的特殊的条件自然会让我们很在意。

其他两段或许没那么好确定，但这个长度为1的第二段就很好考虑了。它一定不能在数组的端点和端点相邻的位置，因为子段需要至少隔一个数字。而当它的位置确定后，我们要做的就是在它的左边和右边分别选一个和最大的子段。等等，这样我们不就把问题解决了？对于每一个可能的中间点，找到最大的左子段和右子段。

最大左子段和最大右子段怎么找。由于枚举中点已经有了O(n)，找这两段就必须是O(1)或者O(logn)。想一下，我们可以预处理每个位置下最大的左子段和最大的右子段。而kadane算法可以以O(n)的时间复杂度完成。

kadane算法

Kadane算法是一种用于解决最大子数组和问题的动态规划算法。它的核心思想是在遍历数组的过程中，维护一个局部最优解，并最终得到全局最优解。

Kadane算法的核心思想是：

对于每个位置i，计算以该位置结尾的最大子数组和

状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])

最终答案：max(dp[0], dp[1], …, dp[n-1])

那么我们就可以用kadane分别预处理左右最大子段

		for(int i=1;i<=n;++i){
			if(i == 1) ldp[i] = a[i];
			else ldp[i] = max(a[i], ldp[i-1] + a[i]);
			if(i == 1) lm[i] = ldp[i];
			else lm[i] = max(lm[i-1], ldp[i]);
		}
		for(int i=n;i>=1;--i){
			if(i == n) rdp[i] = a[i];
			else rdp[i] = max(a[i], rdp[i+1] + a[i]);
			if(i == n) rm[i] = rdp[i];
			else rm[i] = max(rm[i+1], rdp[i]);
		}

这样我们只需要枚举中间子段，就可以得到每一个中间子段对应的最大结果，从而找出最终的答案。

完整代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[500005];
int ldp[500005];
int rdp[500005];
int lm[500005];
int rm[500005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		for(int i=1;i<=n;++i) cin >> a[i];
		memset(ldp, 0, sizeof(ldp));
		memset(rdp, 0, sizeof(rdp));
		memset(lm, 0, sizeof(lm));
		memset(rm, 0, sizeof(rm));
		for(int i=1;i<=n;++i){
			if(i == 1) ldp[i] = a[i];
			else ldp[i] = max(a[i], ldp[i-1] + a[i]);
			if(i == 1) lm[i] = ldp[i];
			else lm[i] = max(lm[i-1], ldp[i]);
		}
		for(int i=n;i>=1;--i){
			if(i == n) rdp[i] = a[i];
			else rdp[i] = max(a[i], rdp[i+1] + a[i]);
			if(i == n) rm[i] = rdp[i];
			else rm[i] = max(rm[i+1], rdp[i]);
		}
		int res = -1e9;
		for(int k=3;k<=n-2;++k){
			res = max(res, a[k]+lm[k-2]+rm[k+2]);
		}
		cout << res << "\n";
	}
	return 0;
}