【最大子段和】变式

ImSakura · 2024-11-27 19:23:47 · 算法·理论

最大子段和

1. 最大子段和

P1115 最大子段和

对于 i 考虑接上或新开一个序列作为最大子段和

f(i)=max（ f(i-1) + a_i , a_i）

2. 最大环状子段和

最大子段和分为2种情况

跨过头尾
未跨过头尾

对于情况2 直接利用#1即可求出

对于情况1 记最大子段和为ans，序列和为sum

并对原序列的所有a_i*-1得到的序列b

对序列b进行一次最大子段和DP操作得到res ，res就是原序列中夹在最大环状子段和之间的部分的相反数

那么环状最大子段和 ans=sum+res
(res是原序列的最小子段和的相反数直接加上序列sum即可)

如图( 方框的部分就是最大子段和 )

以下讲对引用内容进行证明:

假设区间(k,j)不是最小子段和

那么只可能是(k,j)的子区间[x,y]

(因为剩下的已经是最大子段和的区间了)

意味着(k,x),(y,j)的区间和一定是正值(若为负值只会让(k,j)最小值更小于于此矛盾)

因此把这俩个区间并入最大子段和会更优

但是由于前提子段和区间已经是固定下来了的因此这俩个区间和必定 sum_1<0

故(k,j)必为最小子段和

Code:

#include <bits/stdc++.h>
using namespace std;

int a[200005];
int b[200005];

int f[200005];//最大字段和
int g[200005];//最小字段和

int main(){
    int n;
    cin>>n;
    int sum = 0;
    for(int i =1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]*-1;
        sum+=a[i];
    }
    int ans1 = -0x3f;
    int ans2 = -0x3f;

    for(int i =1;i<=n;i++){
        f[i]=max(f[i-1]+a[i],a[i]);
        g[i]=max(g[i-1]+b[i],b[i]);
        ans1=max(ans1,f[i]);
        ans2=max(ans2,g[i]);
    }
    int ans = max(ans1,sum+ans2);
    cout<<ans;
    return 0;
}

3. 双子序列最大子段和

P2642 双子序列最大和枚举中间的数，然后去算左边的最大子段，再算出右边的最大子段，加起来，用打擂法，求出最大值，会 TLE

那怎么办？我们可以预处理

我们可以用 O(n) 的时间计算到前 i 个数的最大子段，

我们可以用 O(n) 的时间计算到后 i 个数的最大子段

cin >> n;
for (int i = 1; i <= n; i++)cin >> x[i];
f[1] = x[1];
for (int i = 2; i <= n; i++)f[i] = max(f[i - 1] + x[i], x[i]); //算最大子段
for (int i = 2; i <= n; i++)f[i] = max(f[i - 1], f[i]); //更新成最大值
l[n] = x[n];
for (int i = n - 1; i >= 1; i--)l[i] = max(l[i + 1] + x[i], x[i]); //算最大子段
for (int i = n - 1; i >= 1; i--)l[i] = max(l[i + 1], l[i]); //更新成最大值

完整Code

#include <bits/stdc++.h>
using namespace std;
long long a[1000005];
long long f[1000005];//最大字段和left
long long g[1000005];//最大字段和right

int main(){
    int n;
    cin>>n;
    for(int i =1;i<=n;i++)cin>>a[i];
    f[1]=a[1];
    for(int i =2;i<=n;i++){
        f[i]=max(f[i-1]+a[i],a[i]);
    }
    for(int i=2;i<=n;i++){
        f[i]=max(f[i],f[i-1]);
    }
    g[n]=a[n];
    for(int i =n-1;i>0;i--){
        g[i]=max(g[i+1]+a[i],a[i]);
    }
    for(int i =n-1;i>0;i--){
        g[i]=max(g[i],g[i+1]);
    }
    long long ans = -0x3f;

    for(int i =2;i<=n-1;i++){
        ans=max(f[i-1]+g[i+1],ans);
    }
    cout<<ans;
    return 0;
}

4. 环状最大两段子段和

P1121 环状最大两段子段和