自动搬运

查看原文

来自洛谷，原作者为

	qwqerty 计算机科学教育新生态。

搬运于2025-08-24 23:11:42，当前版本为作者最后更新于2025-03-23 21:10:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提供一个空间复杂度 $O(1)$ 的做法。

解题思路

本题可以分为两种情况考虑

• 跨环情况：看做从车站 $1$ 坐到车站 $x$，再从车站 $x$ 坐到车站 $n$。也就是说 $x+1$ 至 $y-1$ 的部分是没有坐到的。我们想让坐到的部分最大化，就要让没坐到的部分最小化。求出原序列的最小子段和，再用总和减去即可。这一部分的空间复杂度可以做到 $O(1)$。
• 不跨环情况：相当于直接求最大子段和。这一部分的空间复杂度也是 $O(1)$ 的。

将上面两种情况综合起来，也就是求它们的最小值，就能得到最终答案。
注意特判全是负数的情况，不然会得到 $70$ 分。

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n, maxdp, mindp, sum, minn = LLONG_MAX, maxx = LLONG_MIN, maxn = LLONG_MIN;
signed main() {
	cin >> t;
	while (t--) {
		cin >> n;
		sum += n;
		maxn = max(maxn, n);
		maxdp = max(n, maxdp + n);
		maxx = max(maxdp, maxx);
		mindp = min(n, mindp + n);
		minn = min(mindp, minn);
	}
	if (maxn < 0) cout << maxn;
	else cout << max(sum - minn, maxx);
	return 0;
}