33OJ
登录 注册

2 条题解

  • 1
    @ 2026-11-13 21:32:12

    显然可以O(n)做
    考虑反转有效果当且仅当反转后的最大子段和对应的子段与反转区间有交,且不重合,
    问题就变成了从原数组中选两个不交的最大子段,
    前缀dp一遍,后缀dp一遍,枚举中间分割线求一下对于每一条分割线,左右的最大子段和之和,最大值,即为答案
    代码:

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=5002;
    #define int long long
    int n,a[maxn];
    int dp[maxn],dp2[maxn];
    signed main(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) dp[i]=max(a[i],dp[i-1]+a[i]);
        for(int i=2;i<=n;i++) dp[i]=max(dp[i],dp[i-1]);
        for(int i=n;i>=1;i--) dp2[i]=max(a[i],a[i]+dp2[i+1]);
        for(int i=n-1;i>=1;i--) dp2[i]=max(dp2[i],dp2[i+1]);
        int ans=-0x3f3f3f3f3f3f3f3f;
        for(int i=0;i<=n;i++)  ans=max(ans,dp[i]+dp2[i+1]);
        cout<<ans<<endl;
        return 0;
    }
    

    信息

    ID
    5
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度普及
    标签
    递交数
    4
    已通过
    3
    上传者