fac10_1_2.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 346 页，例
//最大子段和问题的分治算法

 public class Fac10_1_2{
    static int[] a;
    static int besti;
    static int bestj;
     public Fac10_1_2(int[] x,int bi,int bj)
       {
         a=x;
         besti=bi;
         bestj=bj;
       }
   public static int maxSubSum(int left,int right)
   {
    int sum=0;
    if(left==right)sum=a[left]>0? a[left]:0;
    else
      {
    int  center=(left+right)/2;
    int leftsum=maxSubSum(left,center);
    int rightsum=maxSubSum(center+1,right);
    int s1=0;
    int lefts=0; 
    for(int i=center;i>=left;i--){
       lefts+=a[i];
        if(lefts>s1){s1=lefts;besti=i;}
        }
    int s2=0;
    int rights=0;
    for(int i=center+1;i<=right;i++){
        rights+=a[i];
       if(rights>s2){s2=rights;bestj=i;}
        }
          sum=s1+s2;
          if(sum<leftsum)sum=leftsum;
          if(sum<rightsum)sum=rightsum;
        }
      return sum;
   } 
     public static int maxSum()
       {
         return maxSubSum(1,a.length-1);
       }         

      public static void main(String args[])
  {
    int v[]={-2,11,-4,13,-5,-2};
    int w=0;
    int c=0;
    Fac10_1_2 abc=new Fac10_1_2(v,w,c);
    System.out.println("the maxsum is "+abc.maxSum());
    System.out.println(" 注意这里是以零开始计数的");
   System.out.println("the start is "+abc.besti+"  the end is "+abc.bestj); 
  }
}