题解 | #牛客练习赛134#

提供一下我的个人理解，希望对你有帮助，希望大佬们及时更正

#include<bits/stdc++.h>
#define fi first
#define sc second
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;

int n;

void solve()
{
    cin>>n;

    vector<vector<LL>> a(2,vector<LL>(n+2,0));
    vector<LL> sum1(n+2,0),sum2(n+2,0);
    for(int i=0;i<2;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }

    //特殊情况
    if(n==1)
    {
        cout<<a[0][1]+a[1][1]<<endl;
        return;
    }

    //计算第一行前缀和
    for(int i=1;i<=n;i++)
    {
        sum1[i]=(LL)sum1[i-1]+a[0][i];
    }

    //计算第二行后缀和
    for(int i=n;i>=1;i--)
    {
        sum2[i]=(LL)sum2[i+1]+a[1][i];
    }

    vector<LL> mx1(n+2,-1e18); 
    vector<LL> mx2(n+2,-1e18);   
    vector<LL> mx3(n+2,-1e18);
    vector<LL> mx4(n+2,-1e18);
    
    //至于这里为什么是找第二行前i个数的最大值而不是找第一行，个人理解是因为
    //与左侧交换的时候，第一行只是顺序发生了变换，并不影响答案，下面寻找第一行后i个数的最大值同理
    for(int i=1;i<=n;i++)
    {
        mx1[i]=max(mx1[i-1],a[1][i]); //寻找第二行前i个数的最大值
        mx2[i]=max(mx2[i-1],a[1][i]-a[0][i]); //寻找第二行前i列中交换后能获取的最大值，因为
                                              //交换点左边的是第一行的贡献值变成第二行，所以先减去原本第一行对答案的贡献值，再加上第二行的贡献值
                                              //下面交换点右侧同理
    }

    for(int i=n;i>=1;i--)
    {
        mx3[i]=max(mx3[i+1],a[0][i]); //寻找第一行后i个数的最大值
        mx4[i]=max(mx4[i+1],a[0][i]-a[1][i]); //同上
    }

    LL res=-1e18;
    //看看是不是能不交换就能找到最大值
    for(int i=1;i<=n;i++)
    {
        res=max(res,sum1[i]+sum2[i]);
    }

    for(int i=2;i<n;i++)
    {
        //交换点左侧与右侧交换
        res=max(res,(LL)sum1[i]+sum2[i]+mx2[i-1]+mx4[i+1]);
        //交换点与左侧交换，第一行位置交换贡献值不变
        res=max(res,(LL)sum1[i]+sum2[i]-a[1][i]+mx1[i-1]);
        //交换点与右侧交换，第二行位置交换贡献值不变
        res=max(res,(LL)sum1[i]+sum2[i]-a[0][i]+mx3[i+1]);
    }

    //讨论分界点的时候只讨论了2~n-1,把漏掉的第1个和第n个位置加上
    res=max(res,(LL)sum1[1]+sum2[1]-a[0][1]+mx3[2]);
    res=max(res,(LL)sum1[n]+sum2[n]-a[1][n]+mx1[n-1]);

    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}