给你一个整数数组 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

提示：

1 <= nums.length <= 10(5)

-10(4) <= nums[i] <= 10(4)

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

动态规划，dp[i]表示以第i个元素结尾的子数组的最大和

则dp[i+1] = max(nums[i], dp[i]+nums[i])

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

采用分治法

定义一个操作 get(a, l, r) 表示查询 a 序列 [l,r] 区间内的最大子段和

那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)

我们将区间分为两段，当元素只剩一个时开始合并

合并两个区间时想要在o(1)时间求得新区间的ans，我们可以维护四个变量

lAns 表示 [l,r] 内以 l 为左端点的最大子段和

rAns 表示 [l,r] 内以 r 为右端点的最大子段和

ans 表示 [l,r] 内的最大子段和

sum 表示 [l,r] 的区间和

首先sum直接加即可；

lAns有两种情况：（rAns同理）

左区间的lAns；

左区间的sum+右区间的lAns

最后ans就可以通过l.ans、r.ans、l.rAns+r.lAns求得

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
class Solution {
public:
    struct sub {
        int sum, lans, rans, ans;
    };
    sub updaeSub(sub &l, sub &r) {
        int sum = l.sum + r.sum;
        int lans = max(l.lans, l.sum + r.lans);
        int rans = max(r.rans, r.sum + l.rans);
        int ans = max(l.ans, r.ans);
        ans = max(l.rans + r.lans, ans);
        return sub(sum, lans, rans, ans);
    }
    sub get(vector<int> &nums, int l, int r) {
        if (l == r) {
            return sub(nums[l], nums[l], nums[l], nums[l]);
        }
        int m = (r - l) / 2 + l;
        sub lsub = get(nums, l, m);
        sub rsub = get(nums, m + 1, r);
        return updaeSub(lsub, rsub);
    }
    int maxSubArray(vector<int> &nums) {
        return get(nums, 0, nums.size() - 1).ans;
    }
};