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

gnwe1990

问题描述：

有n个数（以下都视为整数），每个数有正有负，现在要在n个数中选取相邻的一段，使其和最大，输出最大的和。

问题分析：

看到这个问题，它是属于带“最”字的问题，其实就是一个求最优解的问题。对于这种问题的朴素算法就是枚举出每种可能，然后在其中寻找一个最优的解，然后输出。因为输出仅要求这个子段的和，因此不必再记录关于解的组成的信息。

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

另附一个可以输出解的具体数据。
  
  一、穷举法：


import java.util.*;
public class LargestSubsegmentSum1
{
public static void main(String[] args)
{
  /**
   *从键盘输入所要求的序列的长度n
   */
  Scanner in=new Scanner(System.in);
  
  System.out.println(&quotlease enter the length of segment you want to make(输入你要求的序列的长度):");
  int n=in.nextInt();
  /**
   *从键盘输入所要求的序列，存储在a[n]中
   */
  int[] a=new int[n];
  System.out.println("Now,please enter the elements of the segment you want(请依次输入这个序列包含的元素(整数)):");
  for(int i=0;i< n;i++)
  {
   a=in.nextInt();
  }
  
        double startTime=System.currentTimeMillis();//starttime
        /**
   *求解最大子段和存在maxSum中
   */
  int maxSum=a[0];
  for(int i=0;i< n-1;i++)
  {
   int temp=a;
   for(int j=i+1;j< n;j++)
   {
    temp+=a[j];
    if(temp>maxSum)
     maxSum=temp;
   }
  }
  double endTime=System.currentTimeMillis();//endtime
  /**
   *打印输出求解结果和程序所用时间
   */
  System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum);
  System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
}
}
二、动态规划
   我们令一个数组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]。



import java.util.*;
public class LargestSubsegmentSum3
{
public static void main(String[] args)
{
  /**
   *从键盘输入所要求的序列的长度n
   */
  Scanner in=new Scanner(System.in);
  
  System.out.println("Please enter the length of segment you want to make(输入你要求的序列的长度):");
  int n=in.nextInt();
  /**
   *从键盘输入所要求的序列，存储在a[n]中
   */
  int[] a=new int[n];
  System.out.println("Now,please enter the elements of the segment you want(现在请依次输入这个序列包含的元素(整数)):");
  int i;
  for(i=0;i< n;i++)
  {
   a=in.nextInt();
  }
  /**
   *求解最大子段和存在maxSum中
   */
  double startTime=System.currentTimeMillis();//starttime
  int maxSum=0;
  /* 我们令一个数组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]。
   */
  int[] b=new int[n];
  b[0]=a[0];
  for(int j=1;j< n;j++)
  {
   if(b[j-1]>0)
    b[j]=b[j-1]+a[j];
   else
   {
    b[j]=a[j];
   }
   if(b[j]>maxSum)
    maxSum=b[j];
  }
  
  double endTime=System.currentTimeMillis();//endtime
  /**
   *打印输出结果和程序运行所用时间
   */
  System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum);
  System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
}
}

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

/**
* @author Wang Ke
*
*/
/**
* 动态规划方法：若记b[j]为从a到a[j]的最大的子段和 （j是定的，“最大”指的是i从1到j-1中，a+...+a[j]最大的），
* 那么所求的max{ a+a[i+1]+...+a[j-1]+a[j] (1<=i< j<=n) } ＝max{ max{
* a+..+a[j] (1<=j<=n) } } ＝max{ b[1],...,b[n] }。 b[]由定义可知：j==1时，b[1]=a[1]；
* j>1时,b[j]=max{ b[j-1]+a[j],a[j] }。
*
*/
public class MaxArray {
    /**
     * @param a
     */
    public static void prtArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a + " ");
        }
        System.out.print("\n");
    }
    /**
     * @param a1
     * @param a2
     * @return
     */
    public static int max(int a1, int a2) {
        if (a1 >= a2 || a1 == a2)
            return a1;
        return a2;
    }
    /**
     * @param n
     * @param b
     * @param a
     * @param beg
     */
    public static void setB(int n, int[] b, int[] a, int[] beg) {
        if (n == 0) {
            b[n] = a[n];
            beg[n] = n;
        } else {
            setB(n - 1, b, a, beg);
            b[n] = max(b[n - 1] + a[n], a[n]);
            if (b[n - 1] + a[n] > a[n])
                beg[n] = beg[n - 1];
            else
                beg[n] = n;
        }
    }
    /**
     * @param a
     */
    public static void maxChildArry(int[] a) {
        int b[] = new int[a.length];
        int beg[] = new int[a.length];
        b[0] = a[0];
        for (int n = 0; n < b.length; n++)
            setB(n, b, a, beg);
        int maxsum = b[getMaxElementIndex(b)];
        System.out.println("MaxSum: " + maxsum);
        PrtMaxChildArry(a, beg[getMaxElementIndex(b)], getMaxElementIndex(b));
    }
    /**
     * @param aa
     * @param beg
     * @param end
     */
    public static void PrtMaxChildArry(int aa[], int beg, int end) {
        System.out.print("The Maxmium Child-Array is: { ");
        for (int i = beg; i <= end; i++) {
            System.out.print(aa + " ");
        }
        System.out.println("}\n");
    }
    /**
     * @param b
     * @return
     */
    public static int getMaxElementIndex(int[] b) {
        // TODO Auto-generated method stub
        int maxele = 0;
        int i;
        for (i = 1; i < b.length; i++) {
            if (b[maxele] < b) {
                maxele = i;
            }
        }
        return maxele;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = { 1, 2, -1, 1, 3, 2, -2, 3, -1, 5, -7, 3, 2, -2, 4 - 5 };
        prtArray(a);
        maxChildArry(a);
    }
}

运行：

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 }