题解：P11963 [GESP202503 六级] 环线

qwqerty · 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;
}