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<int> &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<int>& 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};
};这段代码,希望能通俗易懂一点,主要是逻辑,我自己内心演算算出不来
其实也不难
lSum 表示 [l, r]内以 l为左端点的最大子段和
rSum 表示 [l, r] 内以 r 为右端点的最大子段和
mSum 表示 [l, r] 内的最大子段和
iSum 表示 [l, r] 的区间和
以下简称 [l, m] 为 [l, r] 的「左子区间」,[m + 1, r] 为 [l, r] 的「右子区间」。我们考虑如何维护这些量呢(如何通过左右子区间的信息合并得到 [l, r] 的信息)?对于长度为 1 的区间 [i, i],四个量的值都和 ai 相等。对于长度大于 1 的区间:
首先最好维护的是 iSum,区间 [l, r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
对于 [l, r] 的 lSum,存在两种可能,它要么等于「左子区间」的 lSum,要么等于「左子区间」的 iSum 加上「右子区间」的 lSum,二者取大。
对于 [l, r] 的 rSum,同理,它要么等于「右子区间」的 rSum,要么等于「右子区间」的 iSum 加上「左子区间」的 rSum,二者取大。
当计算好上面的三个量之后,就很好计算 [l, r] 的 mSum 了。我们可以考虑 [l, r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m,也就是说 [l, r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个;它也可能跨越 mm,可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。