f(i) : 以nums[i]结尾的所有区间内元素之和的最大值
f(i) = max(nums[i], f(i-1) + nums[i]);
f(i) = nums[i] + max(f(i-1), 0); 该式子可以不用开数组，而是用一个变量滚动更新f(i) 用last代替f(i-1),并更新f(i)

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

使用分治法（学习分治法思想）

Time : $O(N)$
Space ：$O(logN)$

详细题解看Ipad笔记

class Solution {
public:

    struct Node {
        int sum, s, ls, rs;
        //sum：整个当前区间的总和
        //s：整个的区间的最大连续子段和
        //ls：最大前缀
        //rs：最大后缀
    }; //这里的分号;总是忘记！！！

    Node build(vector<int>& nums, int l, int r) {
        if (l == r) {
            int v = max(nums[l], 0);
            return {nums[l], v, v, v};
        }
        int mid = l + r >> 1;
        auto L = build(nums, l, mid), R = build(nums, mid + 1, r);
        Node res;
        res.sum = L.sum + R.sum;
        res.s = max(max(L.s, R.s), L.rs + R.ls); //这里不是L.sum而是L.rs
        res.ls = max(L.ls, L.sum + R.ls);
        res.rs = max(R.rs, R.sum + L.rs); //这里的R和L与上面一行的L和R全部相反
        return res;
    }
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN; //初始设置为负无穷
        for (auto x : nums) res = max(res, x); //特判所有负数的情况
        if (res < 0) return res;
        Node t = build(nums, 0, nums.size() - 1);
        return t.s;
    }
};