Leetcode 53.最大子序和

题目描述：

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

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

示例 1：

1
2
3

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2

输入：nums = [1]
输出：1

示例 3：

1
2

输入：nums = [0]
输出：0

示例 4：

1
2

输入：nums = [-1]
输出：-1

示例 5：

1
2

输入：nums = [-100000]
输出：-100000

提示：

• $1 <= nums.length <= 3 * 10^4$
• $10^5 <= nums[i] <= 10^5$

链接：

https://leetcode-cn.com/problems/maximum-subarray

题目分析

1.动态规划

  我们用 dp[i] 表示以 nums[i] 结尾的最大子序列和。那么 dp[i] 只有两种情况，第一种是 nums[i] 加上 dp[i-1] 所表示的那一段，第二种是 nums[i] 单独作为新的一段。而我们只需要保留这两种中较大的那一个。也即状态转移方程为 dp[i] = max{dp[i-1]+nums[i], nums[i]}。而我们所要求的结果也即 dp 数组中最大的值。
  另外我们通过观察可以发现，每一个 dp[i] 只取决于 dp[i-1]，并且在遍历的时候便可以边记录最大值，则其实我们无需建立一个 dp 数组，只需要一个变量 pre 来表示每一个 dp[i-1] 即可。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = nums[0];
        int pre = 0;
        for(int i = 0; i < nums.size(); i++){
            pre = max(pre+nums[i], nums[i]);
            result = max(result, pre);
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为数组的长度。因为我们只对数组进行了一次遍历。
  空间复杂度：$O(1)$。我们只需要常数个变量的空间。

2.分治法 - 官方题解

  这是题目中提到的更为精妙的进阶方法，没有想到，参阅了官方题解 最大子序和 - 力扣官方题解。主要思路是利用了线段树，对于每一个区间 [l, r]，维护了 4 个变量，分别是

• $lSum$，表示 [l, r] 中以 l 为左端点的最大子序和。
• $rSum$，表示 [l, r] 中以 r 为右端点的最大子序和。
• $iSum$，表示 [l, r] 的区间和。
• $mSum$，表示 [l, r] 中最大子序和。

  对于每一个区间 [l, r] 这些变量的赋值都来自于 [l, m] 和 [m+1, r] 的这些变量，也即分治后递归回升的整合。具体整合方法为

• $iSum = iSum_l + iSum_r$，也即左右子区间的和即为该区间的和。
• $lSum = max(lSum_l, iSum_l+lSum_r)$，也即要不是左区间的 $lSum$，要不是整个左区间加上右区间的 $lSum$。
• $rSum = max(rSum_r, iSum_r+rSum_l)$，同理，要不是右区间的 $rSum$，要不是整个右区间加上左区间的 $rSum$。
• $mSum = max(mSum_l, mSum_r, rSum_l+lSum_r)$，也即如果 $mSum$ 不跨越 m，则可以是左区间或者是右区间的 $mSum$，如果跨越 m，则是左区间的 $rSum$ 加上右区间的 $lSum$。

  最后递归到最外层，求出 [0, nums.size()-1] 区间的 $mSum$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
    }
};

  时间复杂度：$O(n)$，这样的方法下其实相当于是进行了一颗二叉树的先序遍历。
  空间复杂度：$O(\log n)$，也即递归的深度。

  这样的方法下使用了递归，实际运行的时间比动态规划更长，也需要更多的空间，但是它的意义是它可以解决任意区间下的最大子序和问题，并且建立成为一颗树之后，所有的子区间信息都可以用堆的方法来存储，就可以在 $O(\log n)$ 的时间内找到任意区间的答案。并且假如序列中的某些值发生修改，只需要对有影响的区间值进行修改维护，所需的时间只要 $O(\log n)$，便可以继续使用。这样的特性对于大规模的查询优势便十分明显。