题意

给定一个数组，求其连续子数组的最大和

分析

法一：分治
考虑将数组一分为二，如果解决了左右半区间的子问题，即求出了不跨越中点的最大连续子数组的和，那么只需要将它们和跨越中点的连续子数组的最大和，即可求出原问题的解。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        return solve(0, len-1, nums);
    }

    int solve(int l, int r, vector<int>& nums){
        if(l >= r)return nums[l];
        int mid = l+r>>1;
        int lres = solve(l, mid, nums);
        int rres = solve(mid+1, r, nums);
        int lsum = 0, lmax = -0x7f7f7f7f, rsum = 0, rmax = -0x7f7f7f7f;
        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);
        }

        int cross_max_sum = lmax + rmax;

        return max(cross_max_sum, max(lres, rres));
    }
};

法二：
dp
考虑以第 i 个元素结尾的连续子数组的最大和
f[i] = max(f[i-1] + nums[i], nums[i])
ans = max(f[i])
可以简化为两个变量记录。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int sum = 0;
        int len = nums.size();
        for(int i = 0; i < len; i ++){
            sum = max(sum + nums[i], nums[i]);
            ans = max(ans, sum);
        }

        return ans;
    }
};