求最大子数组时遭遇ArrayIndexOutOfBoundsException错误求助

你遇到的ArrayIndexOutOfBoundsException完全是因为参数传错了类型：

• findMaxSubarray函数要求的low和high是数组的索引值（比如你16个元素的数组，合法索引是0到15），但你的findLow和findHigh函数返回的是数组里的元素值。
• 测试数组里最小元素是-25，把这个负数作为索引传入findMaxSubarray，直接触发了索引越界；同时findHigh返回的20远大于数组最大索引15，后续递归也会出问题。

1. 替换错误的索引参数来源
   直接删掉findLow和findHigh函数，在getMaxSubarray里传入数组的合法索引范围即可：

   public static Triple<Integer,Integer,Integer> getMaxSubarray(int[] arr){
       // 0是数组第一个元素的索引，arr.length-1是最后一个元素的索引
       return findMaxSubarray(arr, 0, arr.length - 1);
   }
   

2. 修复跨中心子数组的求和重复问题
   原findMaxCrossingArray的第二个循环从mid开始，会重复累加arr[mid]的值，导致求和错误，应该从mid+1开始：

   for(int j = mid + 1; j <= high; j++) {
       sum += arr[j];
       if (sum > rightSum) {
           rightSum = sum;
           rightMax = j;
       }
   }
   

3. 初始化优化（可选）
   可以把leftMax初始化为mid、rightMax初始化为mid+1，避免极端情况下（比如全负数数组）的初始值错误。

static Triple<Integer,Integer,Integer> findMaxSubarray(int[] arr, int low, int high){
    if(high == low)
        return new Triple<>(low, high, arr[low]);
    else {
        int mid = low + (high - low) / 2;

        Triple<Integer,Integer,Integer> l = findMaxSubarray(arr, low, mid);
        Triple<Integer,Integer,Integer> r = findMaxSubarray(arr, mid + 1, high);
        Triple<Integer, Integer, Integer> c = findMaxCrossingArray(arr, low, mid, high);
        
        if(l.getLast() >= r.getLast() && l.getLast() >= c.getLast())
            return new Triple<>(l.getFirst(), l.getMiddle(), l.getLast());
        else if(r.getLast() >= l.getLast() && r.getLast() >= c.getLast())
            return new Triple<>(r.getFirst(), r.getMiddle(), r.getLast());
        else
            return new Triple<>(c.getFirst(), c.getMiddle(), c.getLast());
    }
}

static Triple<Integer,Integer,Integer> findMaxCrossingArray(int arr[], int low, int mid, int high){
    int leftSum = Integer.MIN_VALUE, leftMax = mid;
    int rightSum = Integer.MIN_VALUE, rightMax = mid + 1;
    int sum = 0;
    for(int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > leftSum) {
            leftSum = sum;
            leftMax = i;
        }
    }
    sum = 0;
    for(int j = mid + 1; j <= high; j++) {
        sum += arr[j];
        if (sum > rightSum) {
            rightSum = sum;
            rightMax = j;
        }
    }
    return new Triple<>(leftMax, rightMax, leftSum + rightSum);
}

public static Triple<Integer,Integer,Integer> getMaxSubarray(int[] arr){
    return findMaxSubarray(arr, 0, arr.length - 1);
}

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