当前位置：首页 > article >正文

蓝桥杯好题推荐----最大字段和

article 2025/3/17 9:27:48

🌈个人主页：羽晨同学

💫个人格言:“成为自己未来的主人~”

题目链接

P1115 最大子段和 - 洛谷https://www.luogu.com.cn/problem/P1115

解题思路

在这道题目中，我们使用的其实也是前缀和的思想，开始的时候，我创建一个前缀和的数组，然后用前缀和中的最大值-前缀和中的最小值，就是距离的最大值。但是这样子是不可以的，因为我们并没有考虑字段的合理性，

所以，我们还是应该利用前缀和数组，不断地找到距离的最大值，找距离的最大值，我们则用当前的前缀和-前面所找到的前缀和中的最小值。这样就可以保证字段的合理。

代码实现

#include<iostream>
using namespace std;
const int N = 1e6+10;
typedef long long LL;
LL f[N];
LL prevmin=0;//前面的前缀和中的最小值 
LL res = -1e20;//最大的和 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		f[i]=f[i-1]+x;
	}
	for(int i=1;i<=n;i++)
	{
		res = max(res,f[i]-prevmin);
		prevmin = min(prevmin,f[i]);

	}
	cout<<res<<endl;
	return 0;	
}