P1121 环状最大两段子段和

传送门

思路：$dp+$维护前后缀最值。

当两端非跨环时，直接扫一遍$pr{e}_{mx}[i]+su{f}_{mx}[i+1],i\in [1,n)$即可。

当两端跨环，即等价于求中间两端非跨环的最小子段和，直接将$a[i]$取个反，就等价于求最大子段和=$sum+mn$。

此外此题有点细节需要注意：最小段子和不能包含整个区间，也不能将最大子段区间个数变为1个，这样只有一个数，不满足两个非空区间。

$ep:n=4,\{-1,1,-1,-1\}$，这样最小子段和$(-1),(-1,-1)$把$1$包住了只剩一个数不能构成两个区间。

时间复杂度：$O(n)$

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int dp[N],pre[N],suf[N],n,sum,a[N]; int solve(){ int ans=pre[0]=suf[n+1]=-inf; for(int i=1;i<=n;i++) dp[i]=max(dp[i-1]+a[i],a[i]),pre[i]=max(pre[i-1],dp[i]); for(int i=n;i;i--) dp[i]=max(dp[i+1]+a[i],a[i]),suf[i]=max(suf[i+1],dp[i]); for(int i=1;i<n;i++) ans=max(ans,pre[i]+suf[i+1]); return ans; } bool check(){ int cnt=0; for(int i=1;i<=n;i++) cnt+=(a[i]>0); if(cnt==1) return 0; else return 1; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i]; int ans=-inf; ans=solve(); if(!check()) return printf("%d\n",ans),0;//特判剩余的个数不能为1个，不然只有一段. for(int i=1;i<=n;i++ )a[i]=-a[i]; int tmp=solve()+sum; if(!tmp) printf("%d\n",ans);//不能包含整个区间. else printf("%d\n",max(ans,tmp)); return 0; }