LeetCode 53. Maximum Subarray（最大子数组）

原题网址：https://leetcode.com/problems/maximum-subarray/

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

方法一：动态规划/贪心法/Kadane算法，如果是负数，则抛弃前面所有的数字之和，重新开始计算。

public class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        int t = sum;
        for(int i=1; i<nums.length; i++) {
            if (t < 0) t = 0;
            t += nums[i];
            if (t>sum) sum = t;
        }
        return sum;
    }
}

方法二：分治策略。

public class Solution {
    private Result max(int[] nums, int from, int to) {
        Result result = new Result();
        if (from==to) {
            result.max = nums[from];
            result.lmax = nums[from];
            result.rmax = nums[from];
            result.sum = nums[from];
            return result;
        }
        int m = (from+to)/2;
        Result r1 = max(nums, from, m);
        Result r2 = max(nums, m+1, to);
        result.max = Math.max(Math.max(r1.max, r2.max), r1.rmax+r2.lmax);
        result.lmax = Math.max(r1.lmax, r1.sum+r2.lmax);
        result.rmax = Math.max(r1.rmax+r2.sum, r2.rmax);
        result.sum = r1.sum+r2.sum;
        return result;
    }
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Result result = max(nums, 0, nums.length-1);
        return result.max;
    }
}
class Result {
    // 最大和
    int max;
    // 靠左侧最大和
    int lmax;
    // 靠右侧最大和
    int rmax;
    // 数组和
    int sum;
}