fac10_1.java

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

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

 public class Fac10_1{
    static int []a;
    static int besti;
    static int bestj;
      public Fac10_1(int[] x,int bi,int bj)
       {
        a=x;
        besti=bi;
        bestj=bj;
       }
   public static int maxSum()
   {
    int  n=a.length-1;
    int sum=0;
    for(int i=1;i<=n;i++)
     for(int j=i;j<=n;j++){
       int thissum=0;
       for(int k=i;k<=j;k++)thissum+=a[k];
       if(thissum>sum){
          sum=thissum;
          besti=i;
          bestj=j;
        }   
     } 
    return sum;
   }          

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