跬步

题目

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力破解法 O(n^2)

双循环，比较所有连续子集最大值

public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = nums[0];
        for (int j = 0; j < nums.length; j++) {
            int count = 0;
            for (int i = j; i < nums.length; i++) {
                count = count + nums[i];
                max = Math.max(count, max);
            }
        }
        return max;
    }

动态规划法 O(n^2)

循环一次，若当前子集之和小于等于0，那么舍弃之前子集之和，若大于0则累加

public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = nums[0];
        int cur = 0;
        for (int i = 0; i < nums.length; i++) {
            if (cur <= 0 ){
                cur = nums[i];
            }else {
                cur += nums[i];
            }
            max = Math.max(cur,max);
        }
        return max;
    }

分治法 O(n)

循环递归

在每一层递归上都有三个步骤:

1. 分解:将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
2. 解决:若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
3. 合并:将各子问题的解合并为原问题的解。

public int maxSubArray(int[] nums) {
        return find(nums,0,nums.length-1);
    }
public int find(int[] nums,int start, int end){
        if (start == end){
            return nums[start];
        }
        if (start > end){
            return Integer.MIN_VALUE;
        }
        //取中间值
        int middle = (start + end) / 2;
        int leftMax = find(nums,start,middle -1);
        int rightMax = find(nums,middle + 1,end);
        //to left
        int ml = 0;
        for (int i = middle -1,sum = 0;i >= start;i--){
            sum += nums[i];
            ml = Math.max(ml,sum);
        }
        //to right
        int mr = 0;
        for (int i = middle +1,sum = 0;i <= end;i++){
            sum += nums[i];
            mr = Math.max(mr,sum);
        }
        return Math.max(Math.max(leftMax,rightMax),ml+mr+nums[middle]);
    }

个人认为分治法的关键在于将一个大问题分解成解法相同的小问题。如何将问题归纳并分解成为小问题是难点。