举例解释概念:

假设我们有一个序列为:1 2 2 -1 3 (下标从1开始)
那么区间[1,3]的最大连续子段和就是(1 + 2 + 2) = 5
        [2,4]                    (2 + 2) = 4
        [3,5]                    (2 - 1 + 3) = 4

合并区间求最大连续子段和:

区间属性

sum : 区间所有元素的和
tmax : 区间的最大连续子段和
lmax : 以左端点为起点的最大连续子段和 [l,i]
rmax : 以右端点为终点的最大连续子段和 [i,r]

求区间的最大连续子段和tmax:

将区间[l,r]分为两段: [l,mid] [mid + 1,r]
tmax有三种情况。
1.区间的最大连续子段和在左段内部
2.区间的最大连续子段和在右段内部
3.区间的最大连续子段经过mid，横跨左右段.

tr[u].tmax = max(max(tr[lc].tmax,tr[rc].tmax),tr[lc].rmax + tr[rc].lmax);

求lmax,rmax:

将区间[l,r]分为两段: [l,mid] [mid + 1,r]
求端点max有两种情况,这里以lmax为例
1.在左段内部。
2.横跨左右段。

tr[u].lmax = max(tr[lc].lmax,tr[lc].sum + tr[rc].lmax);
tr[u].rmax = max(tr[rc].rmax,tr[rc].sum + tr[lc].rmax);