StackOverFlow发生在分而治之问题中:最大子数组

Question

我试图用分而治之的方法解决最大子数组总和问题，但是发生了运行时错误(StackOverFlow(，我不知道如何处理它，我认为它只是因为我的递归调用而发生的。这是我的方法(错误发生在第一行递归行(：

class Solution {
public int maxSubArray(int[] nums){
int length = nums.length;
int middle = length / 2;
if(length == 1) {
return nums[0];
}
int[] starting = Arrays.copyOfRange(nums, 0, middle+1);
int[] ending = Arrays.copyOfRange(nums, middle +1, length);
int left = maxSubArray(starting);
int right = maxSubArray(ending);
int crossing = computeCrossingSum(starting,ending);
int result = Math.max(left,right);
int finalResult = Math.max(result,crossing);
return finalResult;
}
public int computeCrossingSum (int[] left, int[]right){
int leftS =Integer.MIN_VALUE;
int rightS =Integer.MIN_VALUE;
int leftIndex;
int rightIndex;
int sumS = 0;
for(int i = left.length -1 ; i>=0 ; i--) {
sumS += left[i];
if (sumS > leftS) {
leftS = sumS;
leftIndex = i;
}
}

int sumA = 0;
for(int i = 0 ; i< right.length ; i++){
sumA+=right[i];
if (sumA > rightS){
rightS = sumA;
leftIndex = i;
}
}
int crossingSum = leftS+rightS;
return crossingSum;
}
}

Answer 1

递归调用中的middle + 1从不允许数组大小为 1，因此永远不会满足停止条件。删除+ 1

int[] starting = Arrays.copyOfRange(nums, 0, middle);
int[] ending = Arrays.copyOfRange(nums, middle, length);