最大子数组和，c++简单题提问

class Solution {
public:
struct Status {
int lSum, rSum, mSum, iSum;
};
Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (Status) {lSum, rSum, mSum, iSum};
};

Status get(vector &a, int l, int r) {
if (l == r) {
return (Status) {a[l], a[l], a[l], a[l]};
}
int m = (l + r) >> 1;
Status lSub = get(a, l, m);
Status rSub = get(a, m + 1, r);
return pushUp(lSub, rSub);
}

int maxSubArray(vector& nums) {
return get(nums, 0, nums.size() - 1).mSum;
}
};
这是力扣第53道最大子数组和中的官方解答的第二个方法，分治法，我明白他说的线段数树的意思，但是我的逻辑盘不过来。
来一个负责任的大佬，详细讲解一下Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (Status) {lSum, rSum, mSum, iSum};
};这段代码，希望能通俗易懂一点，主要是逻辑，我自己内心演算算出不来，例如int lSum = max(l.lSum, l.iSum + r.lSum);中我感觉l.lSum不合理我觉得得用l.mSum，int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);而且我觉得会重叠在l.Sum和rsum中。最好能结合线段树讲解一下

首先你要清楚四个变量代表的意义，要想明白为什么要维护这lsum，rsum，isum这三个变量？

pushup的功能是由子节点更新父节点的信息，类似于递归中的回溯。

你问的lsum更新方法，你如果用l.isum+r.msum的话就违背了连续区间的条件了。

这个算法就是为了不违背连续区间的要求，才需要维护四个变量。

两个点将区间分成三部分，最大子段和无非就是下面的四种情况。

• 以l点为起始点，往后一段连续的
• 以r点为结尾的点，往前一段连续的
• 在区间[l, r]内部
• 不以l为起点，不以r为终点。但是经过了中点mid。

这样子你再去想想那4个变量的更新方式

这个题目可以不从线段树的角度来思考，因为它只是分治而没有用到线段树查询，就类似于归并排序。
lSum表示从最左结点开始的最大前缀和，已经有了最大的含义在里面，而l.mSum并不一定是从最左边开始的。
觉得int lSum = max(l.lSum, l.iSum + r.lSum);不好理解，举个例子就明白了：
如果a1=[-2,1]，l.lSum=-2，r.lSum=1，a1.lSum要么等于-2，要么等于-2+1，所以是max(-2,-2+1);
如果a2=[3,4]，l.lSum=3，r.lSum=4，a2.lSum要么等于3，要么等于3+4，所以是max(3,3+4);
再如果a3=[-2,1,3,4]，a3.lSum要么等于a1.lSum，要么等于[-2,1,3]或者[-2,1,3,4]的和。也就是说从-2开始的最大前缀和要么没有超过中线m（就等于a1的最大前缀和），要么超过中线m（此时整个a1就都是最大前缀的一部分了，那就是在a1的基础上继续向后找最大前缀和，就是a1.lSum+a2.lSum，也可以写成a1.iSum+a2.lSum）。

每次pushup的时候，一定是从左子区间的最左结点开始计算最大前缀和。

可以读读这篇文章线段树(Segment Tree)(上) - 知乎