You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

65 lines
2.8 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#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;
}