Java HW StackOverflowError 与从书中复制的 Max Subarray 伪代码

Question

我正在尝试使用直接从我的书中复制的伪代码来实现递归最大子数组问题。我不明白为什么我在 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 个整数的 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. 

Answer 1

这一行:

int mid=(low+high/2);

是错的。应该是

int mid = (low + high) / 2;

看看是否可以解决问题