最大子段和问题的四种算法（暴力法、优化后的暴力法、分治算法、动态规划算法）

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）}=(-2,11,-4,13,-5,-2)时，最大子段和为20。

最大子段和是动态规划中的一种。

import java.util.Random;
import java.util.Scanner;

public class maxSum {
  public static void main(String[] args){

    Scanner scan = new Scanner(System.in);
    Random rd = new Random();

    System.out.println("请输入数据规模n（10的倍数）：");
    int n = scan.nextInt();
    int[] a = new int[n];
    for(int i=0; i<n; i++){
    a[i] = rd.nextInt(20)-10;  
  }//初始化数组，生成-10~10的随机数
  
  /*
  * test暴力法
  */
  long startMili1 = System.currentTimeMillis();
  maxSum ms1 = new maxSum();
  System.out.println("最大子序列和：" + ms1.maxSum(a));
  long endMili1 = System.currentTimeMillis();
  System.out.println("暴力法总耗时："+ (endMili1 - startMili1));
  
  /*
  * test优化后的暴力法
  */
  long startMili2 = System.currentTimeMillis();
  maxSum ms2 = new maxSum();
  System.out.println("最大子序列和：" + ms2.maxSumBF(a));
  long endMili2 = System.currentTimeMillis();
  System.out.println("总耗时："+ (endMili2 - startMili2));
   
  /*
  * test分治算法
  */
  long startMili3 = System.currentTimeMillis();
  maxSum ms3 = new maxSum();
  System.out.println("最大子序列和：" + ms3.maxSumFZ(a));
  long endMili3 = System.currentTimeMillis();
  System.out.println("总耗时："+ (endMili3 - startMili3));

  /*
  * test动态规划算法
  */
  long startMili4 = System.currentTimeMillis();
  maxSum ms4 = new maxSum();
  System.out.println("最大子序列和：" + ms4.MaxSumDynamic(a));
  long endMili4 = System.currentTimeMillis();
  System.out.println("总耗时："+ (endMili3 - startMili3));

  }

  //暴力法(O(n^3))
  public static int maxSum(int a[]){
  int n = a.length - 1;
  int sum = 0;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      int thissum = 0;
      for(int k=i; k<=j; k++){
        thissum += a[k];
      }
      if(thissum>sum){
        sum = thissum;
      }
    }
  }
  return sum;
}

//优化后的暴力法 (O(n^2))
public int maxSumBF(int a[]){
  int n = a.length - 1;
  int sum = 0;
  for(int i=1; i<=n; i++){
    int thissum = 0;
    for(int j=i; j<=n; j++){
      thissum += a[j];
      if(thissum>sum){
        sum = thissum;
      }
    }
  }
  return sum;
}

  //分治算法(n log(n))
  private static int maxSubSum(int a[], int left, int right){
  int sum = 0;
  if(left == right){
     sum = a[left]>0?a[left]:0;
  }else{
    int center = (left + right)/2;
    int leftsum = maxSubSum(a,left,center);
    int rightsum = maxSubSum(a,center+1,right);
    int s1 = 0;
    int lefts = 0;
    for(int i=center; i>=left; i--){
      lefts += a[i];
      if(lefts>s1){
      s1 = lefts;
    }
  }
  int s2 = 0;
  int rights = 0;
  for(int i=center+1; i<=right; i++){
    rights += a[i];
    if(rights>s2){
      s2 = rights;
    }
  }
    sum = s1 + s2;
    f(sum<leftsum){
      sum = leftsum;
    }
    if(sum<rightsum){
      sum = rightsum;
    }
  }
  return sum;
}

public static int maxSumFZ(int a[]){
  return maxSubSum(a,1,a.length-1);
}

//动态规划算法(O(n))
public static int MaxSumDynamic(int a[]){
  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];
  }
  if(b>sum){
    sum = b;
  }
 }
return sum;
}
}