最大子段和问题及其扩展
普通最大子段和
设\(f_i\)表示以\(i\)结尾的最大子段和，则\(f_i=\max\lbrace 0,f_{i-1}\rbrace+a_i\)。
单点修改最大子段和
带单点修改时，用数据结构维护，设\(t[x].lx,t[x].rx,t[x].mx\)分别表示区间\([t[x].l,t[x].r]\)的从左端点为起点的最大子段和，以右端点为起点的最大子段和，区间最大子段和，则容易得到：
\[\left\{ \begin{aligned} t[x].lx&=\max\lbrace t[lc].lx,t[lc].sum+t[rc].lx\rbrace \\ t[x].rx&=\max\lbrace t[rc].rx,t[rx].sum+t[lc].rx\rbrace \\ t[x].mx&=\max\lbrace t[lc].mx,t[rc].mx,t[x].lx,t[x].rx,t[x].sum,t[lc].rx+t[rc].lx\rbrace \end{aligned} \right. \]食用线段树维护，复杂度\(O(n\log n)\)，单点修改线段树自然支持，单次修改\(O(\log n)\)
这样可以查找任意子区间的最大子段和，单次查找\(O(\log n)\)
最小子段和
最小子段和类似于最大子段和，设\(f_i\)表示以\(i\)结尾的最小子段和，则\(f_i=\min\lbrace 0,f_{i-1}\rbrace +a_i\)
环形最大子段和
最大子段和有两种情况，一种是不跨环，此时就是一般最大子段和，另一种是跨环，正难则反，求一个最小子段和，用总和将其减去即可得到。
例子：*****###*,其中是最大子段和，###是最小子段和
两段最大子段和
令\(f_i,g_i\)分别表示以\(i\)为结尾和以\(i\)为开头的最大子段和，则有：
\[\left\{ \begin{aligned} f_i=\max\lbrace 0,f_{i-1}\rbrace+a_i\\ g_i=\max\lbrace 0,g_{i+1}\rbrace+a_i\\ \end{aligned} \right. \]求出解之后，设\(f'_i=\max_{k=1}^if_k\)，\(g'_i=\max_{k=i}^ng_k\)，然后枚举\(i\)取\(f'_i+g'_i\)的最大值即可。时间复杂度\(O(n)\)。
环形两段最大子段和
与环形最大子段和类似，情况如下：设X是最大子段和中的元素，#不是
则
-
XXXX##XXXXX##
- XX####XXXX##XX
同样，求普通的两段最大子段和\(p\)，两段最小子段和\(q\)，\(Ans=\max\lbrace p,\sum_{i=1}^na_i-q\rbrace\)
int f[N],g[N],f1[N],g1[N],s[N],t[N],s1[N],t1[N],sum,a[N],ans1[N],ans2[N],n,ans=-1e9;
memset(f,0xcf,sizeof f);
memset(g,0xcf,sizeof f);
memset(s,0x3f,sizeof f);
memset(t,0x3f,sizeof f);
memset(f1,0xcf,sizeof f);
memset(g1,0xcf,sizeof f);
memset(s1,0x3f,sizeof f);
memset(t1,0x3f,sizeof f);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)sum+=a[i];
for(int i=1;i<=n;i++)f[i]=max(0,f[i-1])+a[i],f1[i]=max(f1[i-1],f[i]);
for(int i=n;i>=1;--i)g[i]=max(0,g[i+1])+a[i],g1[i]=max(g1[i+1],g[i]);
for(int i=1;i<=n;i++)s[i]=min(0,s[i-1])+a[i],s1[i]=min(s1[i-1],s[i]);
for(int i=n;i>=1;--i)t[i]=min(0,t[i+1])+a[i],t1[i]=min(t1[i+1],t[i]);
for(int i=1;i<=n;i++)ans1[i]=g1[i+1]+f1[i];
for(int i=1;i<=n;i++)ans2[i]=sum-s1[i]-t1[i+1];
for(int i=1;i<=n;i++)if(!ans2[i])ans2[i]=-0x3f3f3f3f;
for(int i=1;i<n;i++)ans=max(ans,max(ans1[i],ans2[i]));
cout<<ans;