|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 2e5 + 5;
|
|
|
int n, a[N];
|
|
|
|
|
|
//线段树用的结构体
|
|
|
struct Node {
|
|
|
int l, r; // 区间的左右端点
|
|
|
int lmax; // 区间内紧靠左端点的最大子段和
|
|
|
int rmax; // 区间内紧靠右端点的最大子段和
|
|
|
int tmax; // 区间内的最大值
|
|
|
int sum; // 区间内最大子段和
|
|
|
} tr[N << 2];
|
|
|
|
|
|
//求三个元素的最大值
|
|
|
inline int max(int a, int b, int c) {
|
|
|
return max(max(a, b), c);
|
|
|
}
|
|
|
|
|
|
//从子孙节点汇集信息
|
|
|
void pushup(int u) {
|
|
|
//区间和等于左儿子+右儿子的区间和
|
|
|
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
|
|
|
// u的左侧最大子段和=max(左儿子的左侧最大子段和,左儿子的总和+右儿子的左侧最大子段和)
|
|
|
tr[u].lmax = max(tr[u << 1].lmax, tr[u << 1].sum + tr[u << 1 | 1].lmax);
|
|
|
// u的右侧最大子段和=max(右儿子的右侧最大子段和,右儿子的总和+左儿子的右侧最大子段和)
|
|
|
tr[u].rmax = max(tr[u << 1 | 1].rmax, tr[u << 1 | 1].sum + tr[u << 1].rmax);
|
|
|
//以u为根的节点,整体子段最大值 = max(左儿子子段最大值,右儿子子段最大值,左儿子右侧后缀和最大值+右儿子左侧前缀和最大值)
|
|
|
tr[u].tmax = max(tr[u << 1].tmax, tr[u << 1 | 1].tmax, tr[u << 1].rmax + tr[u << 1 | 1].lmax);
|
|
|
}
|
|
|
|
|
|
//构建节点u,其维护的是区间[l,r]
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r; //初始化记录左右端点
|
|
|
if (l == r) { //递归出口,只有一个元素
|
|
|
//根据题意不同,写的方法不同
|
|
|
// sum:区间和,就是a[l]或a[r]
|
|
|
// tmax:子段和最大值,因为只有一个,也只能是 a[l]或a[r]
|
|
|
// lamx:前半段后缀和最大值,只能是a[l]或a[r]
|
|
|
// rmax:后半段前缀和最大值,只能是a[l]或a[r]
|
|
|
tr[u].sum = tr[u].tmax = tr[u].lmax = tr[u].rmax = a[l];
|
|
|
return; //递归出口
|
|
|
}
|
|
|
//分治思想
|
|
|
int mid = (l + r) >> 1;
|
|
|
//左儿子,右儿子构建
|
|
|
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
|
|
|
//儿孙构建完成后,向父亲推送更新一下信息
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
/*
|
|
|
构建线段树,基于完全二叉树思想,所以根为1
|
|
|
从数据结构的角度来说,线段树是用一个完全二叉树来存储对应于其每一个区间(segment)的数据。
|
|
|
该二叉树的每一个结点中保存着相对应于这一个区间的信息。同时,线段树所使用的这个二叉树是用
|
|
|
一个数组保存的,与堆(Heap)的实现方式相同。
|
|
|
*/
|
|
|
build(1, 1, n);
|
|
|
//输出1~n区间内的最大子段和
|
|
|
cout << tr[1].tmax;
|
|
|
return 0;
|
|
|
} |