网站首页 文章专栏 子序列问题
子序列问题
创建于:2020-07-11 16:00:00 更新于:2022-12-09 10:52:54 羽瀚尘 812
算法题目 算法题目

最大子序和

leetcode 题号:53

题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

解答

解法一

从左往右单次扫描

关键点:要意识到有负数存在,所以可能从左向右加会加成一个负数,那么继续向右移动时,就可以舍弃左边和为负数或0的子序列,重新开始。

如果固执地采用双指针,需要判断双指针移动的条件,会比较复杂,暂时未形成AC的解法。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, res = INT_MIN;
        for(auto m : nums){
            if(sum > 0)
                sum += m;
            else
                sum = m;
            res = max(res, sum);
        }
        return res;
    }
};

解法二

分治法(这里参考官方解法)

这个分治方法类似于「线段树求解 LCIS 问题」的 pushUp 操作。 也许读者还没有接触过线段树,没有关系,方法二的内容假设你没有任何线段树的基础。当然,如果读者有兴趣的话,推荐看一看线段树区间合并法解决 多次询问 的「区间最长连续上升序列问题」和「区间最大子段和问题」,还是非常有趣的。

我们定义一个操作 get(a, l, r) 表示查询 aa 序列 [l, r][l,r] 区间内的最大子段和,那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢?对于一个区间 [l, r][l,r],我们取 m = \lfloor \frac{l + r}{2} \rfloorm=⌊ 
2
l+r
​   
⌋,对区间 [l, m][l,m] 和 [m + 1, r][m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 11 的时候,递归「开始回升」。这个时候我们考虑如何通过 [l, m][l,m] 区间的信息和 [m + 1, r][m+1,r] 区间的信息合并成区间 [l, r][l,r] 的信息。最关键的两个问题是:

我们要维护区间的哪些信息呢?
我们如何合并这些信息呢?
对于一个区间 [l, r][l,r],我们可以维护四个量:

lSum 表示 [l, r][l,r] 内以 ll 为左端点的最大子段和
rSum 表示 [l, r][l,r] 内以 rr 为右端点的最大子段和
mSum 表示 [l, r][l,r] 内的最大子段和
iSum 表示 [l, r][l,r] 的区间和
以下简称 [l, m][l,m] 为 [l, r][l,r] 的「左子区间」,[m + 1, r][m+1,r] 为 [l, r][l,r] 的「右子区间」。我们考虑如何维护这些量呢(如何通过左右子区间的信息合并得到 [l, r][l,r] 的信息)?对于长度为 11 的区间 [i, i][i,i],四个量的值都和 a_ia 
i
​   
相等。对于长度大于 11 的区间:

首先最好维护的是 iSum,区间 [l, r][l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
对于 [l, r][l,r] 的 lSum,存在两种可能,它要么等于「左子区间」的 lSum,要么等于「左子区间」的 iSum 加上「右子区间」的 lSum,二者取大。
对于 [l, r][l,r] 的 rSum,同理,它要么等于「右子区间」的 rSum,要么等于「右子区间」的 iSum 加上「左子区间」的 rSum,二者取大。
当计算好上面的三个量之后,就很好计算 [l, r][l,r] 的 mSum 了。我们可以考虑 [l, r][l,r] 的 mSum 对应的区间是否跨越 mm——它可能不跨越 mm,也就是说 [l, r][l,r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个;它也可能跨越 mm,可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。
这样问题就得到了解决。

对于这道题而言,确实是如此的。但是仔细观察「方法二」,它不仅可以解决区间 [0, n - 1][0,n−1],还可以用于解决任意的子区间 [l, r][l,r] 的问题。如果我们把 [0, n - 1][0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来,即建成一颗真正的树之后,我们就可以在 O(\log n)O(logn) 的时间内求到任意区间内的答案,我们甚至可以修改序列中的值,做一些简单的维护,之后仍然可以在 O(\log n)O(logn) 的时间内求到任意区间内的答案,对于大规模查询的情况下,这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。
class Solution {
public:
    struct status {int lsum, rsum, msum, isum;};
    status push_up(status l, status r){
        status mystatus;
        mystatus.isum = l.isum + r.isum;
        mystatus.lsum = max(l.lsum, l.isum + r.lsum);
        mystatus.rsum = max(r.rsum, r.isum + l.rsum);
        mystatus.msum = max(max(l.msum, r.msum), l.rsum + r.lsum);
        return mystatus;
    }
    status get(vector<int> &nums, int l, int r){
        if(l == r) return (status){nums[l], nums[l], nums[l], nums[l]};
        int mid = (l + r) / 2;
        status lstatus = get(nums, l, mid);
        status rstatus = get(nums, mid + 1, r);
        return push_up(lstatus, rstatus);
    }
    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).msum;
    }
};

官方解中的isum, lsum, rsum, msum相加比较复杂,容易绕晕。 本分治法比较新颖,需要后续好好看。

相关的其他问题: - 线段树求解 LCIS 问题 - 区间最长连续上升序列问题 - 区间最大子段和问题