【动态规划-Kadane】【贪心】【线段树数据结构&&分治】力扣53.最大子数组和

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

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

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

示例 2：
输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

Kadane算法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for(int &num : nums){
            pre = max(pre + num, num);
            maxAns = max(maxAns,pre);
        }
        return maxAns;
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。

在这段代码中，max(pre + num, num)意思是，当pre为负数的时候，pre + num肯定会小于num，这时候就取较大值num，也等同于先让pre为0，然后再继续加上num，也就是说当pre为负数的时候就舍去。pre的作用和下面贪心算法的sum类似，当sum < 0的时候，就让sum = 0，然后继续sum + num。

贪心算法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = -1e4;
        int sum = 0;
        for(int i = 0;i < nums.size(); i++){
            sum += nums[i];
            result = max(result, sum);
            if(sum < 0){
                sum = 0;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

贪心比较好理解，不多赘述，时间复杂度和空间复杂度等同于Kadane。

分治算法

class Solution {
public:
    struct Status {
        int iSum,mSum,rSum,lSum;
    };

    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{iSum,mSum,rSum,lSum};
    };

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

时间复杂度： O(n)
空间复杂度：O(logn)

以示例3为例子画采用分治的方法画线段树：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P3A8e77g-1722274958799)(https://i-blog.csdnimg.cn/direct/31c2196e63ce417d85760abcb69abdae.png)]

Sum 表示 [l,r] 内以 l 为左端点的最大子段和
rSum 表示 [l,r] 内以 r 为右端点的最大子段和
mSum 表示 [l,r] 内的最大子段和
iSum 表示 [l,r] 的区间和

代码中int m = (l + r) >> 1的意思是二进制整体向右移动一位，也就是相当于(l+r)/2并向下取整。

iSum：线段树节点的元素之和，也就是等于左子节点的元素之和加上右子节点的元素之和

int iSum = l.iSum + r.iSum;
1

lSum：线段树节点以l为左端点的最大子段和，这时候有两种情况，一种是左子节点的lSum，也就是右子节点的lSum为负数成分较大的时候，左子节点的lSum一般就是该节点的lSum。第二种情况是右子节点的lSum为正数成分较大的时候，lSum就会等于左子节点的元素之和iSum加上右子树的lSum。

int lSum = max(l.lSum, l.iSum + r.lSum);
1

rSum同理lSum

int rSum = max(r.rSum, r.iSum + l.rSum);
1

mSum表示 [l,r] 内的最大子段和，这时候有三种情况，一种是他的左子节点的mSum等于他的mSum，第二种是他的右子节点的mSum等于他的mSum，第三种是从m的两边都取元素作为子段元素，这时他的mSum = 左子节点的rSum + 右子节点的lSum，将三者进行比较，取最大值返回就是题目的解。

int mSum = max(max(l.mSum,r.mSum), l.rSum + r.lSum);
1

斜体字引用于 ：力扣官方解题
「方法二」相较于「方法一」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。那么这种方法存在的意义是什么呢？
对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间 [0,n−1]，还可以用于解决任意的子区间 [l,r] 的问题。如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一棵真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。