提供一个空间复杂度

O(1)

的做法。

解题思路

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

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

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

70

分。

AC 代码

CPP

#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;
}

题解：P11963 [GESP202503 六级] 环线

文章操作

解题思路

AC 代码

相关推荐

评论

题解：P11963 [GESP202503 六级] 环线