1 package digui_fenzhi;  2   3 //最大字段和  4 import java.util.Random;  5 import java.util.Scanner;  6   7 class SimpleAlgorithm//简单算法  8 {  9      int maxSum(int[] a) 10     {  11         int sum=0; 12         for(int i=0;i<a.length;i++)  13             for(int j=i;j<a.length+1;j++)    14             {    15                 int thissum=0; 16                 for(int k=i;k<j;k++)  17                     thissum+=a[k]; 18                 if(thissum>sum) 19                 {   20                     sum=thissum; 21                 }   22         } 23         return sum; 24     } 25 } 26  27 class DivideConquer//分治法 28 { 29     private int maxSubSum(int[] a,int left,int right) 30     { 31         int sum=0; 32         int s1=0,s2=0,lefts=0,rights=0; 33         int center,leftsum,rightsum; 34         if(left==right) 35         { 36             if(a[left]>0) 37                 sum=a[left]; 38             else 39                 sum=0; 40         } 41         else 42         { 43             center=(left+right)/2;               //划分 44             leftsum=maxSubSum(a,left,center);       //对应情况1，递归求解 45             rightsum=maxSubSum(a,center+1,right);      //对应情况2，递归求解 46             //求解s1 47             for(int i=center;i>=left;i--) 48             { 49                 lefts=lefts+a[i]; 50                 if(lefts>s1) 51                     s1=lefts; 52             } 53             //再求解s2 54             for(int j=center+1;j<=right;j++) 55             { 56                 rights=rights+a[j]; 57                 if(rights>s2) 58                     s2=rights; 59             } 60             sum=s1+s2;                //计算情况3的最大子段和 61             if(sum<leftsum) 62                 sum=leftsum; 63             if(sum<rightsum) 64                 sum=rightsum; 65         } 66         return sum; 67     } 68      int maxSum(int[] a) 69     { 70         return maxSubSum(a,0,a.length-1); 71          72     } 73 } 74  75 class DynamicProgramming//动态规划法 76 { 77      int maxSum(int[] a) 78     { 79         int sum=0; 80         int b=0; 81         for(int i=0;i<a.length;i++) 82         { 83             if(b>0) b+=a[i]; 84             else b=a[i]; 85             if(b>sum)sum=b; 86         } 87         return sum; 88     } 89  90 } 91  92 class Optimal{//判断最优算法 93     public void  Judge(long time1,long time2,long time3){ 94         long b=time1; 95         if(time1 > time2){ 96             b = time2; 97         } 98         if(b > time3){ 99             b = time3;100         }101         if(b==time1){102             System.out.println("最优算法是简单算法！");103         }104         else if(b== time2){105             System.out.println("最优算法是分治算法！");106         }107         else if(b== time3){108             System.out.println("最优算法是动态规划算法！");109         }110         111     }112 }113 public class SubSegment {114     public static void main(String[] args) {115         System.out.println("请输入整数个数n:");116         Scanner in = new Scanner(System.in);117         int n = in.nextInt();118          int a1[]=new int[n+1];119          int a2[]=new int[n+1];120          int a[]=new int[n+1];121          Random random = new Random();122          System.out.println("得到的随机数是：");123          for(int i=0;i<=n;i++)    124          {         125              a1[i] =(int)Math.floor((random.nextDouble()*10.0));   //产生0-10之间随机数    126              a2[i] =(int)Math.floor((random.nextDouble()*10.0));   //产生0-10之间随机数    127              a[i]=a1[i]-a2[i];128              System.out.print(a[i]+" ");129          }130          SimpleAlgorithm s = new SimpleAlgorithm();131          DivideConquer d = new DivideConquer();132          DynamicProgramming p = new DynamicProgramming();133          134          long start1= System.currentTimeMillis();135          System.out.println(" ");136          System.out.println("简单算法算得最大字段和为：\n"+s.maxSum(a));137          long end =System.currentTimeMillis();138          long time = (end - start1);139          System.out.println("用时：" + time + "毫秒！");140          141          long start2 = System.currentTimeMillis();142          System.out.println("分治算法算得最大字段和为：\n"+d.maxSum(a));143          long end1 =System.currentTimeMillis();144          long time1 = (end1 - start2);145          System.out.println("用时：" + time1 + "毫秒！");146          147          long start3 = System.currentTimeMillis();148          System.out.println("动态规划算法算得最大字段和为：\n"+p.maxSum(a));149          long end2=System.currentTimeMillis();150          long time2 = (end2- start3);151          System.out.println("用时：" + time2 + "毫秒！");152          153          Optimal o = new Optimal();154          o.Judge(time, time1, time2);155 156     }157 158 }