分治法求：数列最大子序列，出错，求解，谢谢！

Question

分治法求：数列最大子序列，出错，求解，谢谢！
代码出错信息如下：package com.datastructures.capt0020;  
  
public class MaxSubSum {  
  
   
   
    private static int maxSumRec(int[] a, int left, int right){  
        if(left==right)//Base case  
            if(a[left]>0) return a[left];  
            else return 0;  
        int center = (left+right)/2;  
        int maxLeftSum=maxSumRec(a,left,center);  
        int maxRightSum=maxSumRec(a,center,right);  
          
        int maxLeftBorderSum = 0, leftBorderSum=0;  
        for(int i=center;i>=left;i--){  
            leftBorderSum+=a[i];  
            if(leftBorderSum>maxLeftBorderSum)  
                maxLeftBorderSum = leftBorderSum;  
        }  
        int maxRightBorderSum=0, rightBorderSum=0;  
        for(int i=center+1;i<=right;i++){  
            rightBorderSum+=a[i];  
            if(rightBorderSum>maxRightBorderSum)  
                maxRightBorderSum=rightBorderSum;  
        }  
        return maxLeftSum>maxRightSum?(maxLeftSum>(maxLeftBorderSum+maxRightBorderSum)?maxLeftSum:(maxLeftBorderSum+maxRightBorderSum))  
                                     :(maxRightSum>(maxLeftBorderSum+maxRightBorderSum)?maxRightSum:(maxLeftBorderSum+maxRightBorderSum));  
    }  
    /** 
     * Driver for divide-andconquer maximum contiguous 
     * subsequence sum algorithm. 
     * */  
      
    public static int getMaxSubSum3(int [] a){  
        return maxSumRec(a,0,a.length-1);  
    }  
      
  
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        int [] a = {1,-1,0,2,9,-4,5,7,2,0};  
        System.out.println((0+a.length-1)/2);  
        System.out.println(1/2);  
          
//        //System.out.println(MaxSubSum.getMaxSubSum1(a));  
//        System.out.println(MaxSubSum.getMaxSubSum2(a));  
        System.out.println(MaxSubSum.getMaxSubSum3(a));  
//        System.out.println(MaxSubSum.getMaxSubSum4(a));  
        // TODO Auto-generated method stub  
  
    }  
  
}  /*错误信息：
 * Exception in thread "main" java.lang.StackOverflowError
at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:13)
at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:17)
at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:18)
at com.datastructures.capt0020.MaxSubSum.maxSumRec(MaxSubSum.java:18)
 * */

Answer 1

-Xss2M
添加一个参数，默认堆栈的内存只有64K所以会溢出，设置2M试试~ 

Answer 2

这个溢出是因为出死循环了， 楼上两位没有分析算法哦～
这里出的错：
  int maxRightSum=maxSumRec(a,center,right); 

Answer 3

改过来了，把书上的另外3中球子序列的算法也贴出来了～， 如下：package com.datastructures.capt0020;public class MaxSubSum { /**
 * Cubic maximum contiguous subsequence sum algorithm.
 * algorithm time complication: (N*N*N+3N*N+2N)/6
 * */
public static int getMaxSubSum1(int [] a){

int maxSum = 0;
for(int i=0; i<a.length; i++){
for(int j=i; j<a.length; j++){
int thisSum = 0;
for(int k=i;k<=j;k++){
thisSum += a[k];
}
if(maxSum<thisSum) maxSum = thisSum;
}
}
//int [] a = {1,1,3,-5,9,-4,3,10};
return maxSum;
}

/**
 * Quadratic maximum contiguous subsequence sum algorithm
 * algorithm time complication: O(N*N)
 * {1,1,3,-5,9,-7,-4,3,10,-8,3};
 * */
public static int getMaxSubSum2(int[] a){
int maxSum = 0;
for(int i=0; i<a.length; i++){
int thisSum = 0;
for(int j=i; j<a.length; j++){  
thisSum+=a[j];
if(thisSum>maxSum) maxSum=thisSum;
}
}
return maxSum;
}

/**
 *Recursive maximum contiguous subsequence sum algorithm.
 *Finds maximum sum in subarrary spnning a[left..right].
 *Does not attempt to maintain actual best sequence. 
 *algorithm time complication: O(N log N)
 */
private static int maxSumRec(int[] a, int left, int right){
if((left==right))//Base case
if(a[left]>0) return a[left];
else return 0;
else if((left+1)==right)
return a[left]>=a[right]?a[left]:a[right];
int center = (left+right)/2;
int maxLeftSum=maxSumRec(a,left,center);
int maxRightSum=maxSumRec(a,center,right);

int maxLeftBorderSum = 0, leftBorderSum=0;
for(int i=center;i>=left;i--){
leftBorderSum+=a[i];
if(leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
int maxRightBorderSum=0, rightBorderSum=0;
for(int i=center+1;i<=right;i++){
rightBorderSum+=a[i];
if(rightBorderSum>maxRightBorderSum)
maxRightBorderSum=rightBorderSum;
}
return maxLeftSum>maxRightSum?(maxLeftSum>(maxLeftBorderSum+maxRightBorderSum)?maxLeftSum:(maxLeftBorderSum+maxRightBorderSum))
 :(maxRightSum>(maxLeftBorderSum+maxRightBorderSum)?maxRightSum:(maxLeftBorderSum+maxRightBorderSum));
}
/**
 * Driver for divide-andconquer maximum contiguous
 * subsequence sum algorithm.
 * */

public static int getMaxSubSum3(int [] a){
return maxSumRec(a,0,a.length-1);
}

/**
 * Liner-time max imum contiguous subsequence sum algorithm
 * 该算法的一个附带的优点是，它只对数据进行一次扫描，一旦a[i]被读入并被处理，他就不需要在被存储，
 * 所以，当数组在磁盘或通过互联网传送时，就可以按照顺序读入，在内存中不被储存数组的任何部分，。而且在任何时刻该算法都可以
 * 对已经读入的数据给予序列问题的正确答案（其他几个不具有这个特征），具有这个特征的算法叫联机算法（on-line algorithm）.
 * 仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法
 * */

public static int getMaxSubSum4(int [] a){
int maxSum = 0, thisSum=0;
for(int j=0; j<a.length;j++){
thisSum+=a[j];
if(thisSum>maxSum) maxSum=thisSum;
else if(thisSum<0) thisSum=0;
}
return maxSum;
}

/**
 * @param args
 */
public static void main(String[] args) {
int [] a = {1,1,3,-5,-4,3,3};
System.out.println((0+a.length-1)/2);

System.out.println(MaxSubSum.getMaxSubSum1(a));
System.out.println(MaxSubSum.getMaxSubSum2(a));
System.out.println(MaxSubSum.getMaxSubSum3(a));
System.out.println(MaxSubSum.getMaxSubSum4(a));
// TODO Auto-generated method stub }}

Answer 4

package com.datastructures.capt0020;public class MaxSubSum { /**
 * Cubic maximum contiguous subsequence sum algorithm.
 * algorithm time complication: (N*N*N+3N*N+2N)/6
 * */
public static int getMaxSubSum1(int [] a){

int maxSum = 0;
for(int i=0; i<a.length; i++){
for(int j=i; j<a.length; j++){
int thisSum = 0;
for(int k=i;k<=j;k++){
thisSum += a[k];
}
if(maxSum<thisSum) maxSum = thisSum;
}
}
//int [] a = {1,1,3,-5,9,-4,3,10};
return maxSum;
}

/**
 * Quadratic maximum contiguous subsequence sum algorithm
 * algorithm time complication: O(N*N)
 * {1,1,3,-5,9,-7,-4,3,10,-8,3};
 * */
public static int getMaxSubSum2(int[] a){
int maxSum = 0;
for(int i=0; i<a.length; i++){
int thisSum = 0;
for(int j=i; j<a.length; j++){  
thisSum+=a[j];
if(thisSum>maxSum) maxSum=thisSum;
}
}
return maxSum;
}

/**
 *Recursive maximum contiguous subsequence sum algorithm.
 *Finds maximum sum in subarrary spnning a[left..right].
 *Does not attempt to maintain actual best sequence. 
 *algorithm time complication: O(N log N)
 */
private static int maxSumRec(int[] a, int left, int right){
if((left==right))//Base case
if(a[left]>0) return a[left];
else return 0;
//else if((left+1)==right)
//return a[left]>=a[right]?a[left]:a[right];
int center = (left+right)/2;
int maxLeftSum=maxSumRec(a,left,center);
int maxRightSum=maxSumRec(a,center+1,right);  //漏了 +1

int maxLeftBorderSum = 0, leftBorderSum=0;
for(int i=center;i>=left;i--){
leftBorderSum+=a[i];
if(leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
int maxRightBorderSum=0, rightBorderSum=0;
for(int i=center+1;i<=right;i++){
rightBorderSum+=a[i];
if(rightBorderSum>maxRightBorderSum)
maxRightBorderSum=rightBorderSum;
}
return maxLeftSum>maxRightSum?(maxLeftSum>(maxLeftBorderSum+maxRightBorderSum)?maxLeftSum:(maxLeftBorderSum+maxRightBorderSum))
 :(maxRightSum>(maxLeftBorderSum+maxRightBorderSum)?maxRightSum:(maxLeftBorderSum+maxRightBorderSum));
}
/**
 * Driver for divide-andconquer maximum contiguous
 * subsequence sum algorithm.
 * */

public static int getMaxSubSum3(int [] a){
return maxSumRec(a,0,a.length-1);
}

/**
 * Liner-time max imum contiguous subsequence sum algorithm
 * 该算法的一个附带的优点是，它只对数据进行一次扫描，一旦a[i]被读入并被处理，他就不需要在被存储，
 * 所以，当数组在磁盘或通过互联网传送时，就可以按照顺序读入，在内存中不被储存数组的任何部分，。而且在任何时刻该算法都可以
 * 对已经读入的数据给予序列问题的正确答案（其他几个不具有这个特征），具有这个特征的算法叫联机算法（on-line algorithm）.
 * 仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法
 * */

public static int getMaxSubSum4(int [] a){
int maxSum = 0, thisSum=0;
for(int j=0; j<a.length;j++){
thisSum+=a[j];
if(thisSum>maxSum) maxSum=thisSum;
else if(thisSum<0) thisSum=0;
}
return maxSum;
}

/**
 * @param args
 */
public static void main(String[] args) {
int [] a = {1,1,3,-4,-5,-4,3,3};
System.out.println((0+a.length-1)/2);

System.out.println(MaxSubSum.getMaxSubSum1(a));
System.out.println(MaxSubSum.getMaxSubSum2(a));
System.out.println(MaxSubSum.getMaxSubSum3(a));
System.out.println(MaxSubSum.getMaxSubSum4(a));
// TODO Auto-generated method stub }}