分治算法，最大子数组问题？？


package b;public class FindMaxCrossingSub {
static int nosum=0;
public static final int MAXLEFTID=0,MAXRIGHTID=1,MAXSUM=2;

public static int[] crossSub(int[] A,int low,int mid,int right){
int sum=0;
int[] cross=new int[3];
int leftSum=0,rightSum=0;
int maxLeft=0,maxRight=0;
//find maxleft
for(int i=mid;i>=low;i--){
sum+=A[i];
if(sum>leftSum){
leftSum=sum;
maxLeft=i;
}else{
leftSum=0;
maxLeft=mid;
}

}
//find maxright
sum=0;
for(int i=mid+1;i<=right;i++){
sum+=A[i];
if(sum>rightSum){
rightSum=sum;
maxRight=i;
}else{
rightSum=0;
maxRight=mid;
}
}
//modify value array
cross[MAXLEFTID]=maxLeft;
cross[MAXRIGHTID]=maxRight;
cross[MAXSUM]=leftSum+rightSum;
System.out.println("leftsum:"+leftSum+",rightsum:"+rightSum);
return cross;
}

public static void print(int[] temp){
for(int i=0;i<temp.length;i++){
System.out.println("no "+i+":"+temp[i]);
}
}

public static int[] findMax(int[] A,int left,int right){
nosum++;
System.out.println("第"+nosum+"次递归调用:"+"left:"+left+"right:"+right);
//System.out.println(Thread.currentThread().getStackTrace()[1].getMethodName());
int mid;
int[] valueArray=new int[3];
int[] leftArray=new  int[3];
int[] rightArray=new int[3];
int[] crossArray=new int[3];
if(left==right){
valueArray[MAXLEFTID]=left;
valueArray[MAXRIGHTID]=right;
valueArray[MAXSUM]=A[left];
return  valueArray;
}else{
mid=(int) Math.floor((left+right)/2);
leftArray=findMax(A,left,mid);
rightArray=findMax(A,mid+1,right);
crossArray=crossSub(A,left,mid,right);
if((leftArray[MAXSUM]>rightArray[MAXSUM])&&(leftArray[MAXSUM]>crossArray[MAXSUM]))
return leftArray;
else if((rightArray[MAXSUM]>leftArray[MAXSUM])&&(rightArray[MAXSUM]>crossArray[MAXSUM]))
return rightArray;
else return crossArray;
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] value=new int[3];
int[] c={1,3,1,-1};
print(c);
value=findMax(c,0,c.length-1);
//print(cross);
System.out.println("---max subArray---");
for(int i=value[0];i<=value[1];i++)
System.out.println("A["+i+"]:"+c[i]);
System.out.print("最大子数组和为："+value[2]);
}}