《最大子段和问题研究》

· · 个人记录

AIM 1:最大子段和

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

例题：P1115最大子段和

难度：普及-

思想：dp

令 p_i 为以位置 i 结尾的最大子段和，看是否延续 p_{i-1} 的最大字段。 

#include<bits/stdc++.h>
using namespace std;
int p[200010];
int main(){
    int n,ans=-10000000,a;
    cin>>n>>a;
    p[1]=a;
    for(int i=2;i<=n;i++){
        cin>>a;
        p[i]=max(a,p[i-1]+a);
        ans=max(p[i],ans);
    }
    cout<<ans;
    return 0;
}

AIM 2：最大双子段和

给定一个长度为 n 的序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大。

例题：P2642双子序列最大和

难度：普及/提高-

正着反着各遍历一遍，令 g_i 为以位置 i 开头的最大字段和。

接着枚举两个子段的分界点，不断更新答案。

注意这种问题有两个子段不能连续和可以连续两种限制，处理方式有些许不同。

#include<bits/stdc++.h>
#define N 1000010
#define int long long
using namespace std;
int n,ans=-LONG_LONG_MAX;
int a[N],f[N],g[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[1]=a[1],g[n]=a[n];
    for(int i=2;i<=n;i++) f[i]=max(f[i-1],0ll)+a[i];
    for(int i=2;i<=n;i++) f[i]=max(f[i],f[i-1]);
    for(int i=n-1;i;i--) g[i]=max(g[i+1],0ll)+a[i];
    for(int i=n-1;i;i--) g[i]=max(g[i],g[i-1]);
    for(int i=2;i<n;i++) ans=max(ans,f[i-1]+g[i+1]);//此处为不能连续的处理方式
    cout<<ans;
    return 0;
}

AIM 3:环状最大子段和

与最大子段和不同的是，在环状序列中我们认为第 1 项与最后一项相邻。

未发现例题

考虑两种情况：子段过端点或不过端点。

不过端点即为 \texttt{AIM 1}，过端点就求序列总和减去最小子段和。

求最小字段和就是将序列取反，再求一遍最大子段和。

取两种情况的答案进行比较。

AIM 4:环状最大两段子段和

给出一段长度为 n 的环状序列 a，即认为 a_1 和 a_n 是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。

例题：P1121环状最大两段子段和

难度：普及+/提高

还是分两种情况如下：

0000111110000011111000
1111000111110000011111

第一种情况就是 \texttt{AIM 2}。

对于第二种情况，求最小两段子段和，就是取反然后求最大两段子段和。

#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n,a[N],f[N],g[N],ans=-INT_MAX,ans2=-INT_MAX,sum;
void get(){
    f[1]=a[1],g[n]=a[n];
    for(int i=2;i<=n;i++) f[i]=max(f[i-1],0)+a[i];
    for(int i=n-1;i;i--) g[i]=max(g[i+1],0)+a[i];
    for(int i=2;i<=n;i++) f[i]=max(f[i],f[i-1]);
    for(int i=n-1;i;i--) g[i]=max(g[i],g[i+1]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    get();
    for(int i=2;i<=n;i++) ans=max(ans,f[i-1]+g[i]);
    for(int i=1;i<=n;i++) a[i]=-a[i];
    get();
    for(int i=2;i<=n;i++) ans2=max(ans2,f[i-1]+g[i]);
    ans2+=sum;
    if(!ans2) ans2=-INT_MAX;
    cout<<max(ans,ans2);
    return 0;
}