Go语言视频零基础入门到精通

javalearner

问题描述：  有n个数（以下都视为整数），每个数有正有负，现在要在n个数中选取相邻的一段，使其和最大，输出最大的和。 问题分析：  看到这个问题，它是属于带“最”字的问题，其实就是一个求最优解的问题。对于这种问题的朴素算法就是枚举出每种可能，然后在其中寻找一个最优的解，然后输出。因为输出仅要求这个子段的和，因此不必再记录关于解的组成的信息。

网上有很多方法，这里选二种。

另附一个可以输出解的具体数据。
  
   
   
     
   

     
   
  
   一、穷举法：

1. import java.util.*;
   
2. public class LargestSubsegmentSum1
   
3. {
   
4. public static void main(String[] args)
   
5. {
   
6.   /**
   
7.    *从键盘输入所要求的序列的长度n
   
8.    */
   
9.   Scanner in=new Scanner(System.in);
   
10.   
    
11.   System.out.println("Please enter the length of segment you want to make(输入你要求的序列的长度):");
    
12.   int n=in.nextInt();
    
13.   /**
    
14.    *从键盘输入所要求的序列，存储在a[n]中
    
15.    */
    
16.   int[] a=new int[n];
    
17.   System.out.println("Now,please enter the elements of the segment you want(请依次输入这个序列包含的元素(整数)):");
    
18.   for(int i=0;i< n;i++)
    
19.   {
    
20.    a[i]=in.nextInt();
    
21.   }
    
22.   
    
23.         double startTime=System.currentTimeMillis();//starttime
    
24.         /**
    
25.    *求解最大子段和存在maxSum中
    
26.    */
    
27.   int maxSum=a[0];
    
28.   for(int i=0;i< n-1;i++)
    
29.   {
    
30.    int temp=a[i];
    
31.    for(int j=i+1;j< n;j++)
    
32.    {
    
33.     temp+=a[j];
    
34.     if(temp>maxSum)
    
35.      maxSum=temp;
    
36.    }
    
37.   }
    
38.   double endTime=System.currentTimeMillis();//endtime
    
39.   /**
    
40.    *打印输出求解结果和程序所用时间
    
41.    */
    
42.   System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum);
    
43.   System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
    
44. }
    
45. }

复制代码

二、动态规划
    我们令一个数组b，b[j]表示前j个元素能组成的最大和。如果b[j-1]大于零，则不管a[j]的情况， b[j-1]都可以向正方向影响，因此可以将a[j]加在b[j-1]上。如果b[j-1]小于零，则不管a[j]再大， 都会产生负影响，因此我们还不如直接令b[j]=a[j]。

1. import java.util.*;
   
2. public class LargestSubsegmentSum3
   
3. {
   
4. public static void main(String[] args)
   
5. {
   
6.   /**
   
7.    *从键盘输入所要求的序列的长度n
   
8.    */
   
9.   Scanner in=new Scanner(System.in);
   
10.   
    
11.   System.out.println("Please enter the length of segment you want to make(输入你要求的序列的长度):");
    
12.   int n=in.nextInt();
    
13.   /**
    
14.    *从键盘输入所要求的序列，存储在a[n]中
    
15.    */
    
16.   int[] a=new int[n];
    
17.   System.out.println("Now,please enter the elements of the segment you want(现在请依次输入这个序列包含的元素(整数)):");
    
18.   int i;
    
19.   for(i=0;i< n;i++)
    
20.   {
    
21.    a[i]=in.nextInt();
    
22.   }
    
23.   /**
    
24.    *求解最大子段和存在maxSum中
    
25.    */
    
26.   double startTime=System.currentTimeMillis();//starttime
    
27.   int maxSum=0;
    
28.   /* 我们令一个数组b，b[j]表示前j个元素能组成的最大和。如果b[j-1]大于零，则不管a[j]的情况，
    
29.    * b[j-1]都可以向正方向影响，因此可以将a[j]加在b[j-1]上。如果b[j-1]小于零，则不管a[j]再大，
    
30.    * 都会产生负影响，因此我们还不如直接令b[j]=a[j]。
    
31.    */
    
32.   int[] b=new int[n];
    
33.   b[0]=a[0];
    
34.   for(int j=1;j< n;j++)
    
35.   {
    
36.    if(b[j-1]>0)
    
37.     b[j]=b[j-1]+a[j];
    
38.    else
    
39.    {
    
40.     b[j]=a[j];
    
41.    }
    
42.    if(b[j]>maxSum)
    
43.     maxSum=b[j];
    
44.   }
    
45.   
    
46.   double endTime=System.currentTimeMillis();//endtime
    
47.   /**
    
48.    *打印输出结果和程序运行所用时间
    
49.    */
    
50.   System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum);
    
51.   System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
    
52. }
    
53. }
    

复制代码

三：可以输出解的具体组成信息

1. 
   
2. /**
   
3. * @author Wang Ke
   
4. *
   
5. */
   
6. /**
   
7. * 动态规划方法：若记b[j]为从a[i]到a[j]的最大的子段和 （j是定的，“最大”指的是i从1到j-1中，a[i]+...+a[j]最大的），
   
8. * 那么所求的max{ a[i]+a[i+1]+...+a[j-1]+a[j] (1<=i< j<=n) } ＝max{ max{
   
9. * a[i]+..+a[j] (1<=j<=n) } } ＝max{ b[1],...,b[n] }。 b[]由定义可知：j==1时，b[1]=a[1]；
   
10. * j>1时,b[j]=max{ b[j-1]+a[j],a[j] }。
    
11. *
    
12. */
    
13. public class MaxArray {
    
14.         /**
    
15.          * @param a
    
16.          */
    
17.         public static void prtArray(int[] a) {
    
18.                 for (int i = 0; i < a.length; i++) {
    
19.                         System.out.print(a[i] + " ");
    
20.                 }
    
21.                 System.out.print("
22. ");
    
23.         }
    
24.         /**
    
25.          * @param a1
    
26.          * @param a2
    
27.          * @return
    
28.          */
    
29.         public static int max(int a1, int a2) {
    
30.                 if (a1 >= a2 || a1 == a2)
    
31.                         return a1;
    
32.                 return a2;
    
33.         }
    
34.         /**
    
35.          * @param n
    
36.          * @param b
    
37.          * @param a
    
38.          * @param beg
    
39.          */
    
40.         public static void setB(int n, int[] b, int[] a, int[] beg) {
    
41.                 if (n == 0) {
    
42.                         b[n] = a[n];
    
43.                         beg[n] = n;
    
44.                 } else {
    
45.                         setB(n - 1, b, a, beg);
    
46.                         b[n] = max(b[n - 1] + a[n], a[n]);
    
47.                         if (b[n - 1] + a[n] > a[n])
    
48.                                 beg[n] = beg[n - 1];
    
49.                         else
    
50.                                 beg[n] = n;
    
51.                 }
    
52.         }
    
53.         /**
    
54.          * @param a
    
55.          */
    
56.         public static void maxChildArry(int[] a) {
    
57.                 int b[] = new int[a.length];
    
58.                 int beg[] = new int[a.length];
    
59.                 b[0] = a[0];
    
60.                 for (int n = 0; n < b.length; n++)
    
61.                         setB(n, b, a, beg);
    
62.                 int maxsum = b[getMaxElementIndex(b)];
    
63.                 System.out.println("MaxSum: " + maxsum);
    
64.                 PrtMaxChildArry(a, beg[getMaxElementIndex(b)], getMaxElementIndex(b));
    
65.         }
    
66.         /**
    
67.          * @param aa
    
68.          * @param beg
    
69.          * @param end
    
70.          */
    
71.         public static void PrtMaxChildArry(int aa[], int beg, int end) {
    
72.                 System.out.print("The Maxmium Child-Array is: { ");
    
73.                 for (int i = beg; i <= end; i++) {
    
74.                         System.out.print(aa[i] + " ");
    
75.                 }
    
76.                 System.out.println("}
77. ");
    
78.         }
    
79.         /**
    
80.          * @param b
    
81.          * @return
    
82.          */
    
83.         public static int getMaxElementIndex(int[] b) {
    
84.                 // TODO Auto-generated method stub
    
85.                 int maxele = 0;
    
86.                 int i;
    
87.                 for (i = 1; i < b.length; i++) {
    
88.                         if (b[maxele] < b[i]) {
    
89.                                 maxele = i;
    
90.                         }
    
91.                 }
    
92.                 return maxele;
    
93.         }
    
94.         /**
    
95.          * @param args
    
96.          */
    
97.         public static void main(String[] args) {
    
98.                 // TODO Auto-generated method stub
    
99.                 int[] a = { 1, 2, -1, 1, 3, 2, -2, 3, -1, 5, -7, 3, 2, -2, 4 - 5 };
    
100.                 prtArray(a);
     
101.                 maxChildArry(a);
     
102.         }
     
103. }
     

复制代码

运行：
  C:ww>java MaxArray
1 2 -1 1 3 2 -2 3 -1 5 -7 3 2 -2 -1
MaxSum: 13
The Maxmium Child-Array is: { 1 2 -1 1 3 2 -2 3 -1 5 }
  

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/2/000635750.zip