分治法

最大子序和

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

示例:

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

public class Status {
    public int lSum, rSum, mSum, iSum;

    public Status(int lSum, int rSum, int mSum, int iSum) {
        this.lSum = lSum; //以 l 为左端点的最大子段和
        this.rSum = rSum; //以 r 为右端点的最大子段和
        this.mSum = mSum; //最大子段和
        this.iSum = iSum; //区间和
    }
}

public int maxSubArray(int[] nums) {
    return dfs(nums, 0, nums.length - 1).mSum;
}

private Status dfs(int[] nums, int left, int right) {
    int[] ans = new int[3];
    if (left == right) {
        return new Status(nums[left], nums[left], nums[left], nums[left]);
    }

    //下面三行分治
    int mid = (left + right) / 2;
    Status l = dfs(nums, left, mid);
    Status r = dfs(nums, mid + 1, right);

    int lSum = Math.max(l.lSum, l.iSum + r.lSum);
    int rSum = Math.max(r.rSum, r.iSum + l.rSum);
    int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
    int iSum = l.iSum + r.iSum;
    return new Status(lSum, rSum, mSum, iSum);
}

hhhhh