分析

• 本题的考点：动态规划、分治。

动态规划

• 考虑状态表示f[i]：表示以nums[i]结尾的最大的连续子数组和。

• 考虑状态转移：$f[i] = max(f[i- 1], 0) + nums[i], 0 < i < n$。

• 我们发现每个状态只和上一个状态有关，因此只是用一个变量f记录每个状态，并在递推过程中记录答案res即可。

分治

• 关于进阶中的分治算法，时间空间都不会优于动态规划，但是其具有拓展性，这里讲解一下。这个题目的拓展可以参考线段树中的AcWing 245. 你能回答这些问题吗。

• 下面是这一题的分治算法讲解。

• 我们对区间进行递归，对于每个区间[l, r]，我们需要记录以下内容：

struct Node {
    int sum;  // 区间总和
    int s;  // 区间最大的连续子数组和
    int ls;  // 区间最大前缀和
    int rs;  // 区间最大后缀和
}

• 根据这些信息我们就可以从子区间构造父区间的信息。具体为什么有这些字段，可以参考线段树中的AcWing 245. 你能回答这些问题吗。

• 结构体内并没有记录区间的两个端点，这是因为我们只需要求解整个区间的最大的连续子数组和，这两个端点会在递归的过程中传下去。

代码

• C++

// 动态规划
class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int f = nums[0], res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            f = max(f, 0) + nums[i];
            res = max(res, f);
        }
        return res;
    }
};

// 分治
class Solution {
public:
    struct Node {
        // 区间总和、区间最大的连续子数组和、区间最大前缀和、区间最大后缀和
        int sum, s, ls, rs;
    };

    // 返回由nums[l, r]构造的Node
    Node build(vector<int> &nums, int l, int r) {

        if (l == r) return {nums[l], nums[l], nums[l], nums[l]};

        int mid = l + r >> 1;
        auto left = build(nums, l, mid), right = build(nums, mid + 1, r);
        Node res;
        res.sum = left.sum + right.sum;
        res.s = max(max(left.s, right.s), left.rs + right.ls);
        res.ls = max(left.ls, left.sum + right.ls);
        res.rs = max(right.rs, right.sum + left.rs);
        return res;
    }

    int maxSubArray(vector<int>& nums) {

        auto t = build(nums, 0, nums.size() - 1);
        return t.s;
    }
};

• Java

// 动态规划
class Solution {
    public int maxSubArray(int[] nums) {

        int f = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            f = Math.max(f, 0) + nums[i];
            res = Math.max(res, f);
        }
        return res;
    }
}

// 分治
class Solution {

    static class Node {
        // 区间总和、区间最大的连续子数组和、区间最大前缀和、区间最大后缀和
        int sum, s, ls, rs;

        public Node() {}
        public Node(int sum, int s, int ls, int rs) {
            this.sum = sum; this.s = s; this.ls = ls; this.rs = rs;
        }
    }

    // 返回由nums[l, r]构造的Node
    private Node build(int[] nums, int l, int r) {

        if (l == r) return new Node(nums[l], nums[l], nums[l], nums[l]);

        int mid = l + r >> 1;
        Node left = build(nums, l, mid), right = build(nums, mid + 1, r);
        Node res = new Node();
        res.sum = left.sum + right.sum;
        res.s = Math.max(Math.max(left.s, right.s), left.rs + right.ls);
        res.ls = Math.max(left.ls, left.sum + right.ls);
        res.rs = Math.max(right.rs, right.sum + left.rs);
        return res;
    }

    public int maxSubArray(int[] nums) {

        Node t = build(nums, 0, nums.length - 1);
        return t.s;
    }
}

时空复杂度分析

• 时间复杂度：动态规划：$O(n)$，n为数组长度。分治：$O(n)$。因为$n+\frac{n}{2}+\frac{n}{4}+… \approx 2 \times n$。

• 空间复杂度：动态规划：$O(1)$。分治：$O(log(n))$。$log(n)$为递归深度。