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

Question

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中。最好能结合线段树讲解一下

Answer 1

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

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

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

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

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

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

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