python/TangDou/AcWing/P1115_XDS.cpp

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