The problem is "Using divide and conquer algorithm, find a maximum subsequence sum."
My question is from the codes below that how it works.
"int maxLeftSum=MaxSub(Alist,Start,Center); "
I'm guessing,
Center =3 , after MaxSub is called Center=1, after MaxSub is called Center =0, then return with 4 ?
============================================================
public class SubSequence{
public static void main(String[] args){
int Alist[]={4,-3,5,-2,-1,2,6,-2};
int Start=0;
int End=Alist.length-1;
int num=MaxSub(Alist,Start ,End );
System.out.println("maxSum is: "+num);
}
public static int MaxSub(int Alist[],int Start,int End){
int leftBordersum=0, rightBordersum=0;
int maxLeftBorderSum=0, maxRightBorderSum=0;
int maxMiddleSum;
if(Start==End)
if(Alist[Start]>0)
return Alist[Start];
else
return 0;
int Center=((Start+End)/2);
int maxLeftSum=MaxSub(Alist,Start,Center);
int maxRightSum=MaxSub(Alist,Center+1,End);
for(int i=Center; i>=Start; i--){ //Counting down
leftBordersum+=Alist[i];
if(leftBordersum>maxLeftBorderSum)
maxLeftBorderSum=leftBordersum;
}
for(int i=Center +1; i<=End; i++){ // Counting up
rightBordersum+=Alist[i];
if(rightBordersum>maxRightBorderSum)
maxRightBorderSum=rightBordersum;
}
maxMiddleSum=maxLeftBorderSum+maxRightBorderSum;
int maxSum=0;
if(maxLeftSum>maxRightSum && maxLeftSum >maxMiddleSum){ //return maxLeftsum
maxSum=maxLeftSum;
}else if(maxRightSum>maxLeftSum && maxRightSum>maxMiddleSum){
maxSum=maxRightSum;
}else if(maxMiddleSum>maxLeftSum && maxMiddleSum>maxRightSum){
maxSum=maxMiddleSum;
}
return maxSum;
}
}