53.maximum-subarray.md

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

示例:

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

---

暴力求解 $O(N^2)$

枚举所有起点和终点，求和取最大

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int res = nums[0];
        for (int i =0; i< n; i++){
            int sum = nums[i];
            res = Math.max(sum, res);
            for (int j = i + 1; j < n; j++){
                sum += nums[j];
                res = Math.max(sum, res);
            }
        }
        return res;
    }
}

提示：

• $ 1 <= nums.length <= 10^5 $

O(N^2) 会 TLE

动态规划 $O(n)$

• f[i] 表示所有以 i 结尾的子数组的最大值
• 状态计算：$ f(i) = max(f(i-1) + nums[i], nums[i]) $

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int f[] = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++){
            f[i] = Math.max(nums[i], f[i-1] + nums[i]);
        }
        return Arrays.stream(f).max().getAsInt();
    }
}

优化空间，在原数组上修改：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1; i < n; i++){
            nums[i] = max(nums[i] , nums[i] + nums[i-1]);
        }
        return *max_element(nums.begin(), nums.end());
    }
};

分治

最大子序和只可能来自于三个 子区间：

• $ [left, mid] $
• $ [mid+1, right] $
• $ (..., mid, mid+1, ...) $，即 一定包含 mid, mid+1 的子区间

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);
    }
};

class Solution {

    int divide(int l , int r , 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 = Math.max(lmax, lsum);
        }
        for (int i = mid+1; i <= r; i++){
            rsum += nums[i];
            rmax = Math.max(rmax, rsum);
        }
        return Math.max(lmax+rmax, Math.max(divide(l , mid, nums), divide(mid+1, r, nums)));
    }

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        return divide(0, n-1, nums);
    }
}