51nod 1254 最大子段和 V2 —

N个整数组成的序列a[1],a[2],a[3],…,a[n]，你可以对数组中的一对元素进行交换，并且交换后求a[1]至a[n]的最大子段和，所能得到的结果是所有交换中最大的。当所给的整数均为负数时和为0。

例如：{-2,11,-4,13,-5,-2, 4}将 -4 和 4 交换，{-2,11,4,13,-5,-2, -4}，最大子段和为11 + 4 + 13 = 28。

Input

第1行：整数序列的长度N（2 <= N <= 50000)

第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）

Output

输出交换一次后的最大子段和。

Input示例

Output示例

28
——————————————————————————————
这道题可以做到O（n） 但是瓶颈在读入

——————————————————————————————

这道题 我们可以枚举右端点 
这个我们先强制我们换的数只能是右端点后面的数（之后把数组倒过来再来一次就可以了）
维护一波后缀和（s【i】表示i-n的和）以及后缀最大值 （mx【i】表示i-n的mx）
那么我们枚举右端点之后 目的自然是求 到i的后缀和s【l】 减去 l到i的区间的最小值（min【l，r】） 的最优解
答案就是s【l】-min【l，r】-s【i+1】+mx【i+1】
那么因为 -s【i+1】+mx【i+1】已知
我们要维护的就是s【l】-mn【l，r】
我们可以利用单调栈维护每个mn所能占领的区间
这样就把数列分成了若干个区间 然后维护区间max（s【l】）
根据每个区间的情况记录最优解 很明显最优解只会越来越优
这样我们每次移动右端点的时候 就用当前端点的值v【i】去弹出栈的元素
然后更新新的区间的信息就好了

#include<stdio.h>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=;

const LL inf=1e15;

char buf[*M],*ptr=buf-;

int read(){

    int ans=,f=,c=*++ptr;

    while(c<''||c>''){if(c=='-') f=-; c=*++ptr;}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=*++ptr;}

    return ans*f;

}

int n;

LL c[M],v[M],s[M],mx[M],mxh,ans;

int cnt;

struct node{LL mn,h;}q[M];

void solve(){

    mxh=-inf; cnt=;

    for(int i=n;i;i--) s[i]=s[i+]+v[i],mx[i]=max(mx[i+],v[i]);

    for(int i=;i<=n;i++){

        LL nowh=s[i];

        while(cnt&&q[cnt].mn>=v[i]) nowh=max(nowh,q[cnt].h),cnt--;

        q[++cnt].mn=v[i]; q[cnt].h=nowh;

        mxh=max(mxh,nowh-v[i]);    ans=max(ans,mxh-s[i+]+mx[i+]);

    }

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=read();

    for(int i=;i<=n;i++) v[i]=read(); v[n+]=-inf;

    for(int i=n;i;i--) s[i]=s[i+]+v[i],mx[i]=max(mx[i+],v[i]);

    solve();

    reverse(v+,v++n);

    solve();

    printf("%lld\n",ans);

    return ;

}

巴特西

51nod 1254 最大子段和 V2 ——单调栈

最新文章

热门文章