StackOverFlow发生分而治之的问题：最大subArray
我试图用分而治之的方法解决最大subArray总和问题，但是发生了运行时错误（StackOverFlow），我不知道如何处理它，我认为这是由于我的递归调用而发生的。这是我的方法（错误发生在第一行递归行）：
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;
}
}
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
你的问题在于递归调用没有正确的终止条件，导致了栈溢出（StackOverflow）。在你提供的代码中，我注意到一个明显的错误是在数组分割时，你尝试复制的范围不正确。这可能导致了意料之外的递归深度增加，从而引发StackOverflowError。
错误的地方在于这两行：
int[] starting = Arrays.copyOfRange(nums, 0, middle 1);
int[] ending = Arrays.copyOfRange(nums, middle 1, length);
这里应该是：
int[] starting = Arrays.copyOfRange(nums, 0, middle);
int[] ending = Arrays.copyOfRange(nums, middle, length);
但是，根据你的描述，实际上可能是想包含middle位置的元素到一边，这样修正为：
int[] starting = Arrays.copyOfRange(nums, 0, middle);
int[] ending = Arrays.copyOfRange(nums, middle, length); // 或者是 middle + 1 如果你想右边不包含middle
确保你的递归逻辑正确地将问题规模减小，并且有明确的终止条件。在你的情况下，当数组长度为1时确实返回了一个值，这是正确的。但请检查是否因为数组分割或处理上的逻辑错误导致了无限递归。
另外，请注意，在computeCrossingSum方法中，你似乎想要计算跨越中间点的最大子数组和，但是在累积sumA时，更新leftIndex应当是笔误，应该是rightIndex。同时，最后计算crossingSum时，你可能漏掉了加号，应为：
int crossingSum = leftS + rightS;
修正这些错误后，你的递归算法应该能正常工作并避免StackOverflowError。如果问题仍然存在，建议使用调试工具逐步执行代码，或者添加日志打印来观察每次递归调用的参数和返回值，以便更准确地定位问题所在。
