题解 P1121 【环状最大两段子段和】
zhy137036
·
·
题解
这题恶评的吧，顶多绿
1.最大子段和
P1115
暴力 O(n^3)，太慢。其中最内层的循环是用来求和的，容易想到用前缀和预处理一下，复杂度优化到 O(n^2)，仍然太慢。
定义 f_i 表示以 i 为尾的子序列中，和最大的那个，即：
f_i=\max_{j=1}^i\sum_{k=j}^ia_k
容易得到，当 i>1 时，f_i=\max(f_{i-1}+a_i,a_i)=\max(f_{i-1},0)+a_i。
定义 $g_i$ 表示 $\max_{k=1}^if_k$，即前 $i$ 个元素构成的序列的最大子段和。
当 $i>1$ 时，$g_i=\max(g_{i-1},f_i)$。
$g_1=f_1
于是得到如下代码：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[200010],f[200010],g[200010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i);
f[1]=a[1];
for(int i=2;i<=n;i++)f[i]=max(f[i-1],0)+a[i];
g[1]=f[1];
for(int i=2;i<=n;i++)g[i]=max(g[i-1],f[i]);
printf("%d\n",g[n]);
return 0;
}
```
## 环状最大子段和
如果这个子段没有跨过 $a_1$ 与 $a_n$ 的分界，那它就是最大子段。
如果跨过了，那另一部分就是没跨过的最小子段。
注意最小子段不能占满整个序列。
解决方法就是 $1\sim n-1$ 求一遍，$2\sim n$ 再求一遍。
求了这么多遍，可以考虑使用函数。
代码：
```cpp
#include<cstdio>
using namespace std;
int n,sum,a[200010],f[200010],g[200010];
int getmax(int*arr,int l,int(*cmp)(int,int)){//指向函数的指针，sort 也是这个原理
f[1]=arr[1];
for(int i=2;i<=l;i++)f[i]=cmp(f[i-1],0)+arr[i];
g[1]=f[1];
for(int i=2;i<=l;i++)g[i]=cmp(g[i-1],f[i]);
return g[l];
}
int max(int x,int y){return x>y?x:y;}//库里的函数好像不能用
int min(int x,int y){return x<y?x:y;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
sum+=a[i];//计算总和
}
int ans=getmax(a,n,max);
ans=max(ans,sum-getmax(a,n-1,min));//用总和减
ans=max(ans,sum-getmax(a+1,n-1,min));
printf("%d\n",ans);
return 0;
}
```
## 最大双子段和
[P2642](/problem/P2642)
从前往后和从后往前维护两个 $f_i$ 和 $g_i$。
然后枚举分界点，找到答案。
顺便可以将 $f_i$ 和 $g_i$ 合并，减少数组数量。
```cpp
#include<cstdio>
#include<algorithm>
#define size 1000010
using namespace std;
int n,a[size],front[size],back[size];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i);
front[1]=a[1];
for(int i=2;i<=n;i++)front[i]=max(front[i-1],0)+a[i];
for(int i=2;i<=n;i++)front[i]=max(front[i-1],front[i]);
back[n]=a[n];
for(int i=n-1;i>0;i--)back[i]=max(back[i+1],0)+a[i];
for(int i=n-1;i>0;i--)back[i]=max(back[i+1],back[i]);
int ans=1ll<<31ll;//溢出为负数
for(int i=2;i<n;i++)ans=max(ans,front[i-1]+back[i+1]);//这样可以保证一定被 a[i] 隔开
printf("%d\n",ans);
return 0;
}
```
## 环状最大双子段和
[P1121](/problem/P1121)
和环状最大子段和类似，分为两种情况。
没有任何一段跨过 $a_1$ 与 $a_n$ 的分界，就是最大双子段和；
有一段跨过 $a_1$ 与 $a_n$ 的分界，就是最小双子段和的补集。
这题坑点在哪呢？**两个子段可以相邻**。
也就是说，最小双子段可以为空。
具体改动见代码。
```cpp
#include<cstdio>
#include<algorithm>
#define size 1000010
using namespace std;
int n,sum,a[size],af[size],ab[size],mf[size],mb[size];
int getmin(int*arr,int l){
mf[1]=arr[1];
for(int i=2;i<=l;i++)mf[i]=min(mf[i-1]+arr[i],min(arr[i],0));//可以为0
for(int i=2;i<=l;i++)mf[i]=min(mf[i-1],mf[i]);
mb[l]=arr[l];
for(int i=l-1;i>0;i--)mb[i]=min(mb[i+1]+arr[i],min(arr[i],0));//可以为0
for(int i=l-1;i>0;i--)mb[i]=min(mb[i+1],mb[i]);
int ans=(1ll<<31ll)-1ll;//2^31-1，即 int 的最大值
for(int i=2;i<l;i++)ans=min(ans,mf[i-1]+mb[i+1]);//这里必须被分开
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
sum+=a[i];
}
af[1]=a[1];
for(int i=2;i<=n;i++)af[i]=max(af[i-1],0)+a[i];
for(int i=2;i<=n;i++)af[i]=max(af[i-1],af[i]);
ab[n]=a[n];
for(int i=n-1;i>0;i--)ab[i]=max(ab[i+1],0)+a[i];
for(int i=n-1;i>0;i--)ab[i]=max(ab[i+1],ab[i]);
int ans=1ll<<31ll;//溢出为负数
for(int i=1;i<n;i++)ans=max(ans,af[i]+ab[i+1]);//可以不被分开
ans=max(ans,sum-getmin(a,n-1));
ans=max(ans,sum-getmin(a+1,n-1));
printf("%d\n",ans);
return 0;
}
```