fac10_1_3.java

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

//本程序取自王晓东编著“算法分析与设计”第 348 页，例
//最大子段问题的动态规划算法

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

      public static void main(String args[])
  {
    int v[]={-2,-3,5,6,-13,11,2,7};
    int w=0;
    int c=0;
    Fac10_1_3 abc=new Fac10_1_3(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);
  }
}