洛谷p1115 最大子段和

题目链接：https://www.luogu.org/problem/P1115

线段树求最大子段和

#include
#include
#include
using namespace std;
#define maxn 200005
#define ll long long
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define inf 0x3f3f3f3f
int a[maxn],sum[maxn<<2],lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2];
//sum 区间和
//msum 区间最大子段和
//lsum 该区间左端点开始的最大子段和
//rsum 该区间右端点开始的最大子段和

inline void pushup(int rt)
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];msum[rt]=max(max(msum[rt<<1],msum[rt<<1|1]),lsum[rt<<1|1]+rsum[rt<<1]);lsum[rt]=max(lsum[rt<<1],sum[rt<<1]+lsum[rt<<1|1]);rsum[rt]=max(rsum[rt<<1|1],sum[rt<<1|1]+rsum[rt<<1]);
}
inline void build(int l,int r,int rt)
{if(l==r){sum[rt]=msum[rt]=lsum[rt]=rsum[rt]=a[l];return ;}int mid=l+r>>1;build(ls);build(rs);pushup(rt);
}
inline int query(int L,int R,int l,int r,int rt)
{if(L<=l&&R>=r)return msum[rt];int ans=-inf,mid=l+r>>1;if(L<=mid)ans=max(ans,query(L,R,ls));if(R>mid)ans=max(ans,query(L,R,rs));return ans;
}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);cout<1,n,1,n,1)<<endl;return 0;
}

转载于:https://www.cnblogs.com/chen99/p/11327155.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！