G6014 [GESP202503 六级] 环线 题解

知识点：动态规划、环形序列、最大子段和。

解题思路

同时计算线性最大非空子段和mx、最小非空子段和mn及总和sum。答案取max(mx,sum-mn)，但全负时只能取mx。

为什么正确

环形最优段要么不跨边界、属于线性最大段，要么为全体减去一段最小线性段；全负特判避免选空段。

易错点

不能把最大值初始化为0；全负情况下sum-mn会错误产生空段。

复杂度

时间O(n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    long long sum=0,mx=LLONG_MIN,mn=LLONG_MAX,curmax=0,curmin=0;
    for(int i=0;i<n;i++) {
        long long x;
        cin>>x;
        sum+=x;
        curmax=max(x,curmax+x);
        mx=max(mx,curmax);
        curmin=min(x,curmin+x);
        mn=min(mn,curmin);
    }
    cout<<(mx<0?mx:max(mx,sum-mn));
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。