65 lines
2.8 KiB
C++
65 lines
2.8 KiB
C++
#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;
|
||
} |