用分治策略解决最大子数组和问题

假设我们有一个数组 arr 包含以下元素：

int arr[] = {1, -3, 2, 1, -1};

我们要找到整个数组的最大子数组和，使用分治算法。分治算法将问题分为三个部分：

左半部分的最大子数组和。
右半部分的最大子数组和。
跨越中间点的最大子数组和。

步骤

1. 计算左半部分的最大子数组和

我们首先计算从 arr[0] 到 arr[mid] 的最大子数组和。假设 mid = 2（即索引值为 2 的位置）。

初始化：
sum = 0
left_sum = INT_MIN
遍历到索引 2（值为 2）：
sum = sum + arr[2] = 0 + 2 = 2
因为 sum 大于 left_sum，所以更新 left_sum为 2
遍历到索引 1（值为 -3）：
sum = sum + arr[1] = 2 + (-3) = -1
因为 sum 小于 left_sum，所以left_sum保持不变
遍历到索引 0（值为 1）：
sum = sum + arr[0] = -1 + 1 = 0
因为 sum 小于 left_sum，所以left_sum保持不变

最终，左半部分的最大子数组和是 2。

2. 计算右半部分的最大子数组和

我们接下来计算从 arr[mid] 到 arr[n - 1] 的最大子数组和。假设 mid = 2（即索引值为 2 的位置）。(n为数组元素个数)

初始化：
sum = 0
right_sum = INT_MIN
遍历到索引 3（值为 1）：
sum = sum + arr[3] = 0 + 1 = 1
因为 sum 大于 right_sum，所以更新 right_sum 为 1
遍历到索引 4（值为 -1）：
sum = sum + arr[3] = 1 + -1 = 0
因为 sum 小于 right_sum，所以right_sum 保持不变

最终，右半部分的最大子数组和是 1。

3. 计算跨越中间点的最大子数组和

我们最后计算跨越中间点的最大子数组和。假设 mid = 2（即值为 2 的位置）。

遍历到索引 2（值为 2）：
sum = sum + arr[2] = 0 + 2 = 2
因为 sum 大于 left_sum，所以更新 left_sum为 2
遍历到索引 1（值为 -3）：
sum = sum + arr[1] = 2 + (-3) = -1
因为 sum 小于 left_sum，所以left_sum保持不变
遍历到索引 0（值为 1）：
sum = sum + arr[0] = -1 + 1 = 0
因为 sum 小于 left_sum，所以left_sum保持不变

最终，左半部分的最大子数组和是 2。

计算右半部分的最大前缀和：我们接下来计算从 arr[mid] 到 arr[n - 1] 的最大子数组和。假设 mid = 2（即值为 2 的位置）。
初始化：
sum = 0
right_sum = INT_MIN
遍历到索引 3（值为 1）：
sum = sum + arr[3] = 0 + 1 = 1
因为 sum 大于 right_sum，所以更新 right_sum 为 1
遍历到索引 4（值为 -1）：
sum = sum + arr[4] = 1 + -1 = 0
因为 sum 大于 right_sum，所以right_sum 保持不变

最终，右半部分的最大子数组和是 1。

计算跨越中间点的最大子数组和：
跨越中间点的最大子数组和为 left_max_suffix_sum + right_max_prefix_sum。
即 2 + 1 = 3

最终，跨越中间点的最大子数组和是3。

结论

通过以上步骤，我们可以计算出整个数组的最大子数组和。左半部分的最大子数组和是 2，右半部分的最大子数组和是 1，跨越中间点的最大子数组和是 3。因此，整个数组的最大子数组和为 max(2, 1, 3) = 3。

通过这个过程，我们可以理解如何使用分治算法计算最大子数组和，并确保正确地找到最大的非负子数组和。

具体实现代码(Java)

public class MaxSubByMyself {
    // 1.创建一个类，获取参数数组，并返回三个参数：数组，最左边索引，最右边索引。√
    // 2.创建一个类，获取上一个类拿到三个参数。对数组元素进行判断：1.只有一个元素，返回靠左边的元素。2.有多个元素，分三种情况：1.答案在左边。2.答案在右边。3.答案跨过中点。第一种和第二种情况直接进行递归。第三种情况可以直接计算出来。
    // 3.创建一个类，专门用于处理答案跨过中点。找到中点，先计算从中点到左边的最大子数组，再计算成从中点到右边的最大子数组。最后把这两个最大子数组相加得到答案。

    public static int maxSubArray(int[] nums) throws Exception {
        if (nums == null || nums.length == 0) {
            throw new Exception("数组不能是空！！！请给出正确的数组笨蛋！！！！");
        }
        return maxSubArray(nums, 0, nums.length - 1);
    }

    private static int maxSubArray(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (left + right) / 2;
        int maxleft = maxSubArray(nums, left, mid);
        int maxright = maxSubArray(nums, mid + 1, right);
        int maxcross = maxcrossSubArray(nums, left, mid, right);

        return Math.max(Math.max(maxleft, maxright), maxcross);
    }

    private static int maxcrossSubArray(int[] nums, int left, int mid, int right) {
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;

        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum){
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;

        for (int i=mid+1;i<=right;i++){
            sum += nums[i];
            if (sum > rightSum){
                rightSum = sum;
            }
        }
        return rightSum+leftSum;


    }

    public static void main(String[] args) throws Exception {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("该数组中最大子数组的和是："+ maxSubArray(nums));
    }
}