[LC]53.最大子数组和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

分析

遍历

用 max 维护最大子数组和，cur_b 维护当前子数组的起始位置，cur 维护当前子数组的和，i 维护当前遍历的位置，每遍历到一个位置，我们将当前位置的值加到 cur 上，然后判断 cur 是否小于 max ，如果大于 max ，则更新 max ，之后再判断 cur 是否小于 0 ，如果 cur 已经小于 0 了，则更新 cur_b 为 i+1 ，然后继续遍历。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max = numeric_limits<int>::min(), cur = 0;
        size_t cur_b = 0;
        for (size_t i = 0; i != nums.size(); ++i)
        {
            cur += nums[i];
            if (cur > max) max = cur;
            if (cur < 0) 
            {
                cur_b = i + 1;
                cur = 0;
            }
        }
        return max;
    }
};

时间复杂度：$O(n)$.

分治

参考leetcode官方题解53. 最大子数组和 - 力扣（LeetCode）。

首先约定对于区间$[l,r]$，$[l, m]$为它的左子区间，$[m + 1, r]$为它的右子区间，其中$m = (l + r) / 2$.

为了求得区间$[l,r]$的最大子数组和，我们可以递归的去求它的左右子区间的最大子数组和，然后想办法获得当前区间的最大子数组和，当前区间的最大子数组和有三种情况：

1. 区间$[l,r]$的最大子数组和等于其左子区间的最大子数组和。
2. 区间$[l,r]$的最大子数组和等于其右子区间的最大子数组和。
3. 区间$[l,r]$的最大子数组和为某个跨越左右子区间的子数组的和。

为了处理情况3，对于每个区间，我们需要维护两个变量$lsum$和$rsum$，其中$lsum$维护了当前区间以$l$为起点的最大子数组和，$rsum$维护了当前区间以$r$为终点的最大子数组和。

有了这两个变量，我们就可以很方便的处理情况3了。即当前区间的最大子数组和应该是其左区间的最大子数组和，右区间的最大子数组和，以及左区间的$rsum$加右区间的$lsum$，这三者取大。

那我们应该如何维护这两个变量呢？不难发现，区间$[l,r]$的$lsum$应该是其左区间的$lsum$和左区间的和加右区间的$lsum$，这两者取大；同理$rsum$应该是右区间的$rsum$和右区间的和加左区间的$rsum$，这两者取大。为了方便，我们额外维护一个变量$isum$用来记录区间和。同时，我们用变量$msum$来维护当前区间的最大子数组和。
$$
\begin{align}
& msum = max(l.msum, r.msum, l.rsum + r.lsum) \\
& isum = l.isum + r.isum \\
& lsum = max(l.lsum, l.isum + r.lsum) \\
& rsum = max(r.rsum, r.isum + l.rsum)
\end{align}
$$
代码

class Solution {
public:
    struct Status
    {
        int lsum, rsum;
        int isum, msum;
    };
    Status maxSubArrayHelper(vector<int> &nums, size_t l, size_t r)
    {
        if (l == r) return {nums[l], nums[l], nums[l], nums[l]};
        size_t m = l + ((r - l) >> 1);
        auto lstatus = maxSubArrayHelper(nums, l, m);
        auto rstatus = maxSubArrayHelper(nums, m + 1, r);
        int isum = lstatus.isum + rstatus.isum;
        int lsum = max(lstatus.lsum, lstatus.isum + rstatus.lsum);
        int rsum = max(rstatus.rsum, rstatus.isum + lstatus.rsum);
        int msum = max(lstatus.rsum + rstatus.lsum, 
                       max(lstatus.msum, rstatus.msum));
        return {lsum, rsum, isum, msum};
    }
    int maxSubArray(vector<int>& nums) {
        auto status = maxSubArrayHelper(nums, 0, nums.size() - 1);
        return status.msum;
    }
};

时间复杂度：

递推方程：$W(n) = 2W(n/2) + O(1)$

由主定理，解得$W(n) = \Theta(n)$.

空间复杂度：

因为采用了递归，所以空间复杂度为递归深度$O(logn)$.

「方法二」相较于「方法一」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。那么这种方法存在的意义是什么呢？

对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间 [0,n−1]，还可以用于解决任意的子区间 [l,r] 的问题。如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一棵真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。

作者：力扣官方题解
链接：https://leetcode.cn/problems/maximum-subarray/solutions/228009/zui-da-zi-xu-he-by-leetcode-solution/
来源：力扣（LeetCode）