题目描述

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

样例

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

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

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

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

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

限制

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

进阶

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

算法1

(动态规划) $O(n)$

1. 设 $f(i)$ 表示以第 $i$ 个数字为结尾的最大连续子序列的 总和 是多少。
2. 初始化 $f(0) = nums[0]$。
3. 转移方程 $f(i) = \max (f(i-1)+nums[i], nums[i])$。可以理解为当前有两种决策，一种是将第 $i$ 个数字和前边的数字拼接起来；另一种是第 $i$ 个数字单独作为一个新的子序列的开始。
4. 最终答案为 $ans = \max (f(k)), 0 \leq k < n$。

时间复杂度

• 状态数为 $O(n)$，转移时间为 $O(1)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储状态。
• 可以通过一个变量来替代数组将空间复杂度优化到常数。

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(), ans;
        vector<int> f(n);
        f[0] = nums[0];
        ans = f[0];

        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1] + nums[i], nums[i]);
            ans = max(ans, f[i]);
        }

        return ans;
    }
};

算法2

(分治) $O(n \log n)$

1. 考虑区间 [l, r] 内的答案如何计算，令 mid = (l + r) / 2，则该区间的答案由三部分取最大值，分别是：
   (1). 区间 [l, mid] 内的答案（递归计算）。
   (2). 区间 [mid + 1, r] 内的答案（递归计算）。
   (3). 跨越 mid 和 mid + 1 的连续子序列。
2. 其中，第 (3) 部分只需要从 mid 开始向 l 找连续的最大值，以及从 mid+1 开始向 r 找最大值即可，在线性时间内可以完成。
3. 递归终止条件显然是 l == r ，此时直接返回 nums[l]。

时间复杂度

• 由递归主定理 $T(n) = 2T(n/2) + O(n)$，解出总时间复杂度为 $O(n \log n)$。
• 或者每一层时间复杂度是 $O(n)$，总共有 $O(\log n)$ 层，故总时间复杂度是 $O(n\log n)$。

空间复杂度

• 需要额外 $O(\log n)$ 的空用于递归的系统栈。

C++ 代码

class Solution {
public:
    int calc(int l, int r, vector<int>& nums) {
        if (l == r)
            return nums[l];
        int mid = (l + r) >> 1;
        int lmax = nums[mid], lsum = 0, rmax = nums[mid + 1], rsum = 0;

        for (int i = mid; i >= l; i--) {
            lsum += nums[i];
            lmax = max(lmax, lsum);
        }

        for (int i = mid + 1; i <= r; i++) {
            rsum += nums[i];
            rmax = max(rmax, rsum);
        }

        return max(max(calc(l, mid, nums), calc(mid + 1, r, nums)), lmax + rmax);
    }

    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        return calc(0, n - 1, nums);
    }
};

算法3

(分治) $O(n)$

1. 对于一个区间 $[l, r]$，维护四个值，分别是：总和 $sum$；非空最大子段和 $s$；前缀非空最大子段和 $ls$；后缀非空最大子段和 $rs$。
2. 分别递归左右子区间。
3. 合并时，对于 $sum$ 则是左右子区间的 $sum$ 之和。
4. 对于 $s$，则有三种情况取最大值：左区间的 $s$；右区间的 $s$；左区间的 $rs$ 加上右区间的 $ls$。
5. 对于 $ls$，则有两种情况取最大值：左区间的 $ls$；左区间的 $sum$ 加上右区间的 $ls$。
6. 对于 $rs$ 同理。
7. 合并后返回递归的结果。

时间复杂度

• 由递归主定理 $T(n) = 2T(n/2) + O(1)$，解出总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(\log n)$ 的空用于递归的系统栈。

struct Node {
    int sum, s, ls, rs;
    Node(int sum_, int s_, int ls_, int rs_) {
        sum = sum_; s = s_; ls = ls_; rs = rs_;
    }
};

class Solution {
public:
    Node solve(int l, int r, const vector<int> &nums) {
        if (l == r)
            return Node(nums[l], nums[l], nums[l], nums[l]);

        int m = (l + r) >> 1;

        Node left = solve(l, m, nums);
        Node right = solve(m + 1, r, nums);

        return Node(
            left.sum + right.sum,
            max(max(left.s, right.s), left.rs + right.ls),
            max(left.ls, left.sum + right.ls),
            max(right.rs, left.rs + right.sum)
        );
    }

    int maxSubArray(vector<int>& nums) {
        return solve(0, nums.size() - 1, nums).s;
    }
};