8.双序列最大子段和

阅读数: 次 2020-10-29

字数：931字 | 预计阅读时长：4分钟

作者：冰糖鸽子

这题差不多算是两道题的结合体

P1091 合唱队型

P1115 最大子段和

没做过的可以先去做一下啊awa

思路

可以枚举中间肯定不取的那个点，枚举 $n$ 次。再计算两边的最大子段和，时间复杂度 $\operatorname{O(n^2)}$ ，期望得分 60

可以发现，以所有 $a_i$ 为开头/结尾（一定包含 $a_i$ ）的最大字段和实可以通过状态转移用 $\operatorname{O(n)}$ 的时间算出来的（后面会讲）

所以先初始化，再枚举中间点的时间复杂度是 $\operatorname{O(n)}$，期望得分 100

实现

求最大子段和的方法很多题解都讲到过，这里再叙述一下：

设 $f_i$ 为以 $a_i$ 结尾的最大子段和

可得到转移方程为（循环从 $1 - n $）：
$$f_i = \max(f_{i-1},0) +a_i $$

设 $f2_i$ 为以 $a_i$ 开头的最大子段和

可得到转移方程为（循环从 $n - 1$）：

$$f2_i = \max(f_{i+1},0) + a_i$$

取上面任意一个数组的最大数则为此数列的最大子段和

下一步，求分割点为 $i$ 的前/后子段中的最大子段和：

设 $l_i$ 为以 $1$ 开头以$a_i$ 结尾的子段中的最大子段和

可得到转移方程为（循环从 $1 - n$）：

$$l_i = \max(l_{i-1},f_i)$$

设 $r_i$ 为以 $a_i$ 开头以 $n$ 结尾的子段中的最大子段和

可得到转移方程为（循环从 $n - 1$）：

$$r_i = \max(r_{i+1},f2_i) $$

枚举中间点 循环从 $2-(n-1)$ ：

$$ans = \max(ans,l_{i-1}+r_{i+1})$$

最后提醒一下，要初始化为负无穷

代码

七个循环虽然很吓人，但每个循环都只有一行代码哦

AC记录-1


//执着换行版

// Problem: P1115 最大子段和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1115
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define maxn 1000010
#define int long long
int n,a[maxn],f[maxn],f2[maxn],l[maxn],r[maxn],sum,ml=-INF,mr=-INF,ans=-INF;
signed main()
{
	cin >> n;
	for(int i = 0;i <= n+2;i++)
	{
		a[i]=f[i]=f2[i]=l[i]=r[i]=-INF;
	}
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=n;i++)
	{
		f[i]=(f[i-1]<0?0:f[i-1])+a[i];
	}
	for(int i=n;i>0;i--)
	{
		f2[i]=(f2[i+1]<0?0:f2[i+1])+a[i];
	}
	for(int i = 1;i <= n;i++)
	{
		l[i]=(l[i-1]<f[i]?f[i]:l[i-1]);
	}
	for(int i = n;i > 0;i--)
	{
		r[i]=(r[i+1]<f2[i]?f2[i]:r[i+1]);
	}
	for(int i = 2;i < n;i++)
	{
		ans=max(ans,l[i-1]+r[i+1]);
	}
	cout << ans;
	return 0;
}

AC记录-2

//开心压行版


// Problem: P1115 最大子段和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1115
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define maxn 1000010
#define int long long
int n,a[maxn],f[maxn],f2[maxn],l[maxn],r[maxn],sum,ml=-INF,mr=-INF,ans=-INF;
signed main()
{
	cin >> n;
	for(int i = 0;i <= n+2;i++){a[i]=f[i]=f2[i]=l[i]=r[i]=-INF;}
	for(int i=1;i<=n;i++){cin >> a[i];}
	for(int i=1;i<=n;i++){f[i]=(f[i-1]<0?0:f[i-1])+a[i];}
	for(int i=n;i>0;i--){f2[i]=(f2[i+1]<0?0:f2[i+1])+a[i];}
	for(int i = 1;i <= n;i++){l[i]=(l[i-1]<f[i]?f[i]:l[i-1]);}
	for(int i = n;i > 0;i--){r[i]=(r[i+1]<f2[i]?f2[i]:r[i+1]);}
	for(int i = 2;i < n;i++){ans=max(ans,l[i-1]+r[i+1]);}
	cout << ans;
	return 0;
}

祝大家 CSP2020 RP++ Score++

本文作者： 益题 Yitee
发布时间： 2020-10-29
最后更新： 2021-08-19
本文标题： 8.双序列最大子段和
本文链接： https://yitee.top/posts/23702.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！