自动搬运

查看原文

来自洛谷，原作者为

	Cripple_Abyss **

搬运于2025-08-24 22:22:33，当前版本为作者最后更新于2020-06-24 22:46:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

这可是省选题呀！！！早知道我也去报名了（但是我报不了QwQ）

题目本质：

• 取若干个前缀和，使他们的和最大

题目做法：

• 暴力枚举：如果前缀和大于$0$，则累加

注：第一个数的前缀和（也就是它本身）不加

时间复杂度：$O(n)$

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,x,s,n;//注意开long long
int main() {
	cin>>n;
	for (ll i=1; i<=n; i++) {
		cin>>x;
		s+=x;
		if (s>0&&i!=1) 
			ans+=s;
	}
	cout<<ans;
	return 0;
}

都看到这里了，点个赞呗QwQ