如何用分治法求解最大子数组和并返回包含索引的数组

原有代码存在三处核心问题需要修正：

• 递归终止条件赋值错误：单元素区间的左右索引应为当前区间端点，和为对应位置的数组值，原代码赋值完全错位
• 跨中点最大子数组计算缺少索引记录：仅统计了左右和，没有记录对应的边界索引
• 缺少三类结果的比较逻辑：需要分别拿到左半区间、右半区间、跨中点三类最大子数组结果，取总和最大的返回

补全后完整代码 #

public class Main {

    public static void main(String[] args) {
        int[] values = {0, 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5,
                -22, 15, -4, 7};
        int low = 1;
        int high = 16;

        int[] LRMax = maxSubarray(values, low, high);
        System.out.println(LRMax[0] + " " + LRMax[1] + " " + LRMax[2]);
    }

    public static int[] maxSubarray(int[] values, int low, int high) {
        // 递归终止条件：区间只有一个元素
        if (high == low) {
            int[] LRMax = new int[3];
            LRMax[0] = low;
            LRMax[1] = high;
            LRMax[2] = values[low];
            return LRMax;
        }

        int mid = (low + high) / 2;
        // 递归获取左半、右半区间的最大子数组结果
        int[] leftPartMax = maxSubarray(values, low, mid);
        int[] rightPartMax = maxSubarray(values, mid + 1, high);
        // 计算跨中点的最大子数组结果
        int[] crossMax = getCrossMax(values, low, mid, high);

        // 比较三类结果，取总和最大的返回
        if (leftPartMax[2] >= rightPartMax[2] && leftPartMax[2] >= crossMax[2]) {
            return leftPartMax;
        } else if (rightPartMax[2] >= leftPartMax[2] && rightPartMax[2] >= crossMax[2]) {
            return rightPartMax;
        } else {
            return crossMax;
        }
    }

    // 单独封装跨中点最大子数组计算逻辑
    private static int[] getCrossMax(int[] values, int low, int mid, int high) {
        int[] crossRes = new int[3];
        // 计算左半部分（含mid）的最大和及对应左边界
        int leftMax = Integer.MIN_VALUE;
        int sum = 0;
        int leftIndex = mid;
        for (int i = mid; i >= low; i--) {
            sum += values[i];
            if (sum > leftMax) {
                leftMax = sum;
                leftIndex = i;
            }
        }
        // 计算右半部分（不含mid）的最大和及对应右边界
        int rightMax = Integer.MIN_VALUE;
        sum = 0;
        int rightIndex = mid + 1;
        for (int i = mid + 1; i <= high; i++) {
            sum += values[i];
            if (sum > rightMax) {
                rightMax = sum;
                rightIndex = i;
            }
        }
        crossRes[0] = leftIndex;
        crossRes[1] = rightIndex;
        crossRes[2] = leftMax + rightMax;
        return crossRes;
    }
}

运行结果 #

上述代码运行后输出8 11 43，对应最大子数组为索引8到11的元素，总和为43，符合预期。

内容的提问来源于stack exchange，提问作者giovanni