我正试图用直接从我的书中复制的伪代码来实现递归Max Subarray问题。我不明白为什么在1次递归之后会出现StackOverFlow问题。这是我的密码。
public class MaxSub {
public int FindMaxCrossingSubArray(ArrayList<Integer> ar, int low, int mid, int high)
{
int maxLeft=0;
int leftSum=Integer.MIN_VALUE;
int sum=0;
for(int i=mid; i>low; i--){
sum= sum + ar.get(i);
if(sum>leftSum){
leftSum=sum;
maxLeft=i;// counter
}
}
int rightSum=Integer.MIN_VALUE;
sum=0;
int MaxRight=0;
for(int j=mid+1; j<=high; j++){
sum=sum+ar.get(j);
if(sum>rightSum){
rightSum=sum;
MaxRight=j;
}
}
System.out.println(maxLeft+MaxRight +"max crossing method");
return maxLeft+MaxRight;
}
public int DivideAndConquerMaxSub(ArrayList<Integer> ar, int low, int high){
if(low==high)//StackOverFlowError
return 0;
else {
int mid=(low+high/2);
int leftSum= DivideAndConquerMaxSub(ar, low, mid);//StackOverFlowError
int rightSum= DivideAndConquerMaxSub(ar, mid+1, high);
int crossSum= FindMaxCrossingSubArray(ar, low, mid, high);
System.out.println(crossSum+ "divide method");
if(leftSum>=rightSum &&leftSum>=crossSum )
return leftSum;
else if (rightSum>=leftSum&&rightSum>=crossSum)
return rightSum;
else
System.out.println(crossSum+ "t");
return crossSum;
}
}
我传入一个从文本文件读取的2000 int的ArrayList。我也试着把它们存储在一个普通的数组中，但仍然得到了同样的错误，所以这和它无关
我在第一行收到StackOverFlow错误：
if(low==high)
然后在线
int leftSum= DivideAndConquerMaxSub(ar, low, mid);
在DivideAndConquerMaxSub方法中。
我的打印输出：
low : 0
high : 2000
1max crossing method
1divide method
1t
Exception in thread "main" java.lang.StackOverflowError
at MaxSub.DivideAndConquerMaxSub(MaxSub.java:54)
at MaxSub.DivideAndConquerMaxSub(MaxSub.java:61)
at MaxSub.DivideAndConquerMaxSub(MaxSub.java:61)
at MaxSub.DivideAndConquerMaxSub(MaxSub.java:61) and so on.
此行：
int mid=（低+高/2）是错误的。它应该是
int mid=（低+高）/2查看是否修复