原题链接

审题

1.连续子序列：子序列必须连续
2.最小长度为1
3.子序列之间至少隔一个数

题解

令 \(presum[i]\) 代表i及其之前的最大前缀和
则第一步更新令 \(presum[i]\) 为必须包括i的最大前缀和，第二步更新令其为i及其之前的最大前缀和。
sufsum同理
最后枚举断点求和

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll presum[1000006]={0},a[1000005]={0},sufsum[1000005]={0};
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) presum[i]=max(presum[i-1]+a[i],a[i]);
    for(int i=2;i<=n;i++) presum[i]=max(presum[i-1],presum[i]);
    sufsum[n+1]=0;
    for(int i=n;i>=1;i--) sufsum[i]=max(sufsum[i+1]+a[i],a[i]);
    for(int i=n-1;i>=1;i--) sufsum[i]=max(sufsum[i+1],sufsum[i]);

    ll ans=-2e18;
    for(int i=2;i<n;i++)
    {
        ans=max(ans,presum[i-1]+sufsum[i+1]);
    }
    cout<<ans;
    return 0;
}